Наивные проверки простоты Оптимизация

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 = 1, 7, 11, 13, 17, 19, 23, 29 (т.е. для i < 30 такое, что gcd (i, 30) = 1).

Кроме вы можете выбрать несколько различных/больше, чем простые числа 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%) Таким образом, он сканирует abo на 20% меньше номеров, поэтому вы ожидаете, что скорость составит не более 20%. Когда вы добавляете в список больше простых чисел, вы получаете уменьшающиеся прибыли.

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