Блог

Главная - Вопросы по программированию - Лучший способ оптимизировать эту самую большую программу с простым коэффициентом

Лучший способ оптимизировать эту самую большую программу с простым коэффициентом

#java #optimization #timeout #prime-factoring

#java #оптимизация #тайм-аут #простой факторинг

Вопрос:

Мне нужна помощь в оптимизации этой программы. Я пытаюсь определить наибольший простой коэффициент для ввода. Однако иногда у нее возникают проблемы с таймаутом, поэтому мне интересно выяснить, как ее оптимизировать.

 import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class PFactor() {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        
        for(int a0 = 0; a0 < t; a0  ){
            long n = in.nextLong();
            System.out.println(pMod(n));
        }
    }

    public static int pMod(long d) {
        long maxVal = 0;
        
        for (long i = 2; i <= d; i  ) {
            if (d % i == 0) {
                boolean prime = pCount(i);
                if (prime == true) {
                    max = i;
                }
            } else {                
                max = max;
            }
        }
        return (int)max;
    }
    
    public static boolean pCount(long inLong) {
        int count = 0;
        for (long s = 1; s <= inLong; s  ) {
            if (inLong % s == 0) {
                count  ;
            } 
        }
        
        if (count == 2) {
            return true;
        } else {
            return false;
        }
    }
}

Знаете ли вы, как оптимизировать этот код, чтобы у него было не так много тайм-аутов? Мне нужно, чтобы это было готово в ближайшее время для кое-чего на работе, поэтому я решил обратиться за помощью, чтобы узнать, могу ли я получить какую-то помощь, поскольку, похоже, я сам не могу понять, где это нуждается в дальнейшей оптимизации.

Комментарии:

1. Извините за некоторые мои грамматические ошибки. Английский не мой родной язык, и я ничего не могу с этим поделать.

2. Вы могли бы начать с того, что не пересчитывали, является ли каждое значение простым каждый раз, проверяя только нечетные делители и разделяя известные факторы, чтобы вы могли быстрее выйти из игры.

3. Как я это сделал? Можете ли вы опубликовать, какие изменения вы бы сделали, чтобы я мог понять, что вы имеете в виду?

4. Начните с реализации сита

5. Я обучаюсь визуальному, поэтому мне обычно нужно, чтобы вы публиковали отредактированные версии исходного кода, чтобы я мог видеть его в действии.

Ответ №1:

Я действительно нашел решение, ребята, после того, как немного повозился с ним! вы все были очень полезны! Спасибо за помощь!