Наивная оптимизация тестирования первичности

Question

У меня есть алгоритм для проверки на простоту, который использует простую реализацию, как указано здесь http://en.wikipedia.org/wiki/Primality_test#Naive_methods

       static boolean check(int n)
   {
           if(n == 2 || n == 3)
           {
                   return true;
           }
           if(n < 2 || n % 2 == 0 || n % 3 == 0)
           {
                   return false;
           }
           for(int i = 6; i * i <= n; i += 6)
           {
                   if(n % (i - 1) == 0 || n % (i + 1) == 0)
                   {
                           return false;
                   }
           }
           return true;
   }

Я прошел весь путь до раздела 6k + 1, но после этогоЯ потерян.Как еще можно оптимизировать это для скорости?

Answer 1

Если вы хотите придерживаться наивного метода, то ваш следующий шаг - использовать следующее свойство, указанное на странице википедии, на которую вы ссылаетесь:

Таким образом, все простые числа имеют вид 30k+ i для i = 1, 7, 11, 13, 17, 19, 23, 29 (т. е. для i <30 такое, что gcd (i, 30) = 1). </p>

За исключением того, что вы могли бывыберите немного другое / больше простых чисел, чем 2.3.5

Замените 6-шаговый цикл на 30-шаговый цикл (и проверьте вручную все простые числа меньше 30)

Код можетвыглядят так:

    static boolean check(int n)
   {
           if(n<30)
           {
              return n==2 || n==3 || n==5 || n==7 || ...
           }

           for(int i = 30; i * i <= n; i += 30)
           {
              if (n % (i + 1))==0 return false;
              if (n % (i + 7))==0 return false;
              if (n % (i + 11))==0 return false;
              if (n % (i + 13))==0 return false;
              if (n % (i + 17))==0 return false;
              if (n % (i + 19))==0 return false;
              if (n % (i + 23))==0 return false;
              if (n % (i + 29))==0 return false;
           }
           return true;
   }

Однако вы заметите, что это сканирует 8/30 (= 27%) чисел, в то время как 6 пошаговых циклов сканирует 2/6 (= 33%), поэтому сканируется около 20% меньше, так что вы ожидаете, что скорость будет увеличена в лучшем случае на 20%.Когда вы добавляете больше простых чисел в список, вы получаете убывающую отдачу.

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