Наибольший простой фактор java

Мне нужна небольшая помощь с этим:

public class BiggestPrimeFactor{
        public static void main(String[] args){
            long biggest=0L;
            for(long i=2L; i<=600851475143L; i++){
                if(600851475143L%i==0){
                    for(int l=1; l<=Math.sqrt(i); l++){
                        if (i%l==0){
                            break;
                        } else{
                            biggest=i;
                        }
                    }
                }
            }
            System.out.println(biggest);
        }
    }//end of BiggestPrimeFactor

Я не знаю, хорошо это или нет, но это занимает слишком много времени (более получаса, потом я устал и закрыл командную строку)...

Можете ли вы помочь или хотя бы сказать мне, все ли в порядке?

Благодарность!

я мог бы решить это!!

вот как это выглядит

public class BiggestPrimeFactor{
public static void main(String[] args){
    long x=600851475143L;
    long biggest=0L;
    for(long i=2L; i<=x; i++){
        for(long l=1L; l<=Math.sqrt(i); l++){
            if(l%i==0){
                break;
            } else{
                while(x%i==0){
                    x=x/i;
                    biggest =i;
                }
            }
        }
    }
    System.out.println(biggest);
}

}//конец BiggestPrimeFactor

и это заняло совсем немного времени! =P спасибо за помощь!


person tobgirado    schedule 28.12.2013    source источник
comment
Это один огромный looooooooooooooooooooooooop.   -  person Maroun    schedule 28.12.2013
comment
@MarounMaroun один ооооооооооооооо не будет проблемой. Core i7 достигает 100 гигафлопс, поэтому завершит работу за 6 секунд . Это второй, вложенный цикл, который превращает 6 секунд в 2-4 дня прогнозируемого времени выполнения. :) (забавно, log(600851475143) ~= 27 вместо 30 дней в месяце, так что без раннего разрыва вложенного цикла он будет работать 2 месяца).   -  person Will Ness    schedule 28.12.2013
comment
зачем тебе твой l?   -  person Will Ness    schedule 29.12.2013
comment
я поставил его, чтобы проверить, был ли i простым или нет   -  person tobgirado    schedule 29.12.2013
comment
вам это не нужно. Кроме того, чтобы сохранить один x%i, вы делаете много l%i.   -  person Will Ness    schedule 30.12.2013
comment
извините, но я не понимаю... я понимаю, что использую много l%i, но я не могу понять, как это сделать без него-..   -  person tobgirado    schedule 30.12.2013


Ответы (2)


Похоже, вы ищете наибольший простой делитель числа 600851475143.

Как только вы нашли простой множитель, вы должны несколько раз разделить на него целевое число. Только когда вы это сделаете, вы должны перейти к проверке дополнительных факторов-кандидатов. Это значительно уменьшит объем работы, который должен выполнять ваш код.

Например, установив, что 600851475143 делится на 71, замените 600851475143 на 600851475143 / 71 = 8462696833 и так далее.

Кроме того, как только множитель будет найден таким образом, он автоматически будет известен как простой. Не будет необходимости в отдельном тесте на простоту (HT @Henry за указание на это).

Вот псевдокод реализации рассматриваемого алгоритма:

n = 600851475143
k = 2
m = None
while n > 1:
  while n % k == 0:
    m = k
    n = n // k               # integer division
  k = k + 2 if k > 2 else 3  # 2, 3, 5, 7, 9, ...
print(m)

(Этот псевдокод оказался действительным Python и на моем компьютере занимает 35 миллисекунд.)

person NPE    schedule 28.12.2013
comment
Кроме того, как только множитель найден таким образом, становится ясно, что он простой. Отдельно проверять на простоту не нужно. - person Henry; 28.12.2013
comment
@ Генри: Действительно. Отличный комментарий, спасибо! - person NPE; 28.12.2013
comment
comment
Спасибо за вашу помощь! - person tobgirado; 29.12.2013

Если вы собираетесь вызывать этот метод несколько раз, вы можете оптимизировать поиск, составив список простых чисел. См. Решето Эратосфена:

http://en.wikipedia.org/wiki/Сито_Эратосфена

Затем начните с наименьшего простого числа, продвигайтесь вверх и остановитесь, когда дойдете до квадратного корня из числа (если вы еще не нашли простой множитель).

person theNinja    schedule 28.12.2013
comment
решая его с помощью сита Er. до sqrt(600G) должно выполняться ~ 2 млн операций (Nlog log N для N=775000). Решение с повторным пробным делением занимает 1437. - person Will Ness; 28.12.2013
comment
К сожалению, я думаю, что использование повторного деления имеет гораздо больше смысла. - person theNinja; 28.12.2013