«простой» алгоритм времени исполнения

Question

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

for(int i = 3; i < 100000; i += 1) 
     if(isPrime(i)) 
      System.out.println(i); 

и занимает 0,52 секунды. Мой друг предложил, чтобы не перебирать для четных чисел:

for(int i = 3; i < 100000; i += 2) 
     if(isPrime(i)) 
      System.out.println(i); 

и занимает 0,53 секунды (возможно случайное значение).

Почему его предложение не сокращает время выполнения? Если я повторю меньшее количество чисел, я бы ожидал, что программа будет работать быстрее.

Код IsPrime():

public static boolean isPrime(int n) 
{ 
    if((n % 2 == 0 && n != 2) || (n % 3 == 0 && n != 3)|| (n % 5 == 0 && n != 5)) 
     return false; 
    for(int i = 5; i < n/5; i += 2) 
    { 
     if(n % i == 0) 
      return false; 
    } 
    return true; 
} 

Answer 1

Кроме алгоритмических проблем, узкие места, скорее всего, писать в System.out потоке. Это трудоемкая задача, я думаю, вы должны оставить эту часть из цикла тестов. Чтобы быстро проверить это, просто закомментируйте (с соответствующим if заявления):

int iterations=100000; 
long time = System.nanoTime(); 
for(int i = 3; i < 100000; i += 2) { //notice: always use curly brackets!!! 
    isPrime(i); 
} 
long endTime = System.nanoTime(); 
System.out.println("Time to go through " + iterations + " iterations: " + (endTime>time?endTime-time:endTime+time)); 
//notice: nanoTime might turn around, resulting in smaller (negative) endTime value 

Кроме того, ответ Томаса гораздо более подробный относительно System.out.print вопроса, а также обеспечивает соответствующий подход конкатенации много строки.

Алгоритмические проблемы:

Если вы собираетесь с ситом Erastothenes подход, вы уже нашли все мелкие штрихи при поиске следующей. Поэтому вы должны хранить их, и вместо того, чтобы проверять каждое нечетное число> 5, вам нужно только проверить те, которые у вас уже есть.

Кроме того, в то же время, вы не должны проверять их все, а только те, которые меньше или равен квадратный корень из вашего номера:

//suppose we have a List<Integer> primeList (populated by previous execution loops) 
// and Integer numberTested as the number under testing 

for(int i=0; i<primeList.size();i++) { 
    if(numberTested%primeList.get(i)==0) { 
     //divider found, not prime 
     break; 
    }   

    if(primeList.get(i)>Math.sqrt(numberTested)) { 
     //still not found a divider -- we found a prime 
     primeList.add(numberTested); 
     break; 
    } 
} 

Каков проблема с этим? Math.sqrt - дорогостоящая операция. Намного дороже, чем умножение ... Итак, если диапазон чисел разрешает (вы должны иметь это всегда в виду!), Мы можем использовать умножение, чтобы быстрее получить сравнение:

sqrt(a)>b === a*a>b, учитывая, что и a, и b - целые положительные числа ,

Integer currentPrimeSquare = primeList.get(i)*primeList.get(i); 
    if(currentPrimeSquare>numberTested) { 
     //still not found a divider -- we found a prime 
     primeList.add(numberTested); 
     break; 
    } 

Для дальнейшего настроить это, вы могли бы хранить квадраты простых чисел тоже - дал вам достаточно памяти ....

Answer 2

Скорее всего, основная часть времени требуется для распечатывания простых чисел в консоль. Таким образом, уменьшение числа проверенных номеров не будет существенно влиять на скорость программы, если количество простых чисел также не уменьшается.

Попытка собрать простые числа в строку и печати, что один раз, как это:

StringBuilder b = new StringBuilder(); 
for(int i = 3; i < 100000; i += 1) 
    if(isPrime(i)) 
     b.append(i).append("\n"); 

System.out.println(b.toString()); 

Answer 3

Может this статья может помочь вам:

boolean isPrime(int n) { 
//check if n is a multiple of 2 
if (n%2==0) return false; 
//if not, then just check the odds 
for(int i=3;i*i<=n;i+=2) { 
    if(n%i==0) 
     return false; 
} 
return true; 
} 

Answer 4

Существует накладные расходы самой виртуальной машины беспокоиться о сравнении времени выполнения Java (например, println может принимать разные периоды при каждом выполнении). Чтобы получить правильное сравнение времени выполнения, запустите каждую тысячу раз и получите средние значения для получения более точных результатов.

Кроме того, реализация Sieve of Erastothenes в Java не так уж трудна, и вы получите очень быстрые результаты, хотя она будет использовать больше памяти.

Answer 5

Если вас интересует наиболее эффективный алгоритм, известный на сегодняшний день, является ли заданное число простым, вам следует рассмотреть вопрос о AKS primality test, который работает в полилогарифмическом времени.

(Этот ответ в основном это повторение another answer на вопрос относительно простоты испытаний.)

Answer 6

1) вы рассматривали использование решета Эратосфена для нахождения простых чисел?

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

3) Ваше заявление, если в простое, если вы проверяете это n = {2,3,5} использовать его, чтобы вернуть результат, который будет препятствовать вам от выполнения остальной части код (не так много времени заставки в данном случае)

4) ваш цикл, вы можете сделать это для г из 7 (состояние на 5 вы уже проверить, и 6 не простое число) в SQRT (п)