Найти простые числа.Простое число, отличное от 6k + 1 6k-1 - PullRequest
Новая
       39

Найти простые числа.Простое число, отличное от 6k + 1 6k-1

0 голосов
/ 11 февраля 2019

Я пытаюсь оптимизировать алгоритм простого поиска.

У меня есть программа, которая находит (считает на самом деле) простые числа ниже некоторого предела.Я знаю, что простое число может быть выражено в форме 6k+1, 6k-1, для некоторых k > 0.

. В настоящее время я использую алгоритм просеивания, чтобы отсортировать не простые числа.Некоторый псевдокод: 

int P[100] = {1};
int m = 100;
int n = 2, k, i, j, sqrtm = (int)sqrt(m);
for(k = 2, i = 5; i < sqrtm + 1; i += k, k ^= 6)
 if(P[i])
  P[i] = 0;
  n = n + 1;
  for(j = i * i; j < m; j += 2 * i)
   P[j] = 0;

for(k = 2, i = 5; i < m + 1; i += k, k ^= 6)
 if(P[i])n = n + 1;

print n;

Над кодом, надеюсь, будет напечатано число простых чисел ниже числа m.Я использую некоторые приемы, чтобы ускорить процесс.Например, начиная отсчет не простых чисел с «5», используйте тот факт, что простое число в приведенной выше форме не может быть кратно «2» и «3».6к + 2 чётно.6k + 3 кратно '3', пусть x = 2k, 6k + 3 => 3x + 3 => 3 (x + 1) mod 3 == 0 или 3 (2k + 1) mod 3 == 0.

Здесь возникает мой вопрос.Если я сделаю предварительное сито с некоторыми простыми числами, могу ли я принять другую форму простого числа, чтобы ускорить цикл просеивания?Например, предварительно просеять с 2,3,5,7,11,13,17,19,23,29.Итак, теперь массив P не имеет кратных выше.Может быть, кто-то может предложить мне какую-то форму простого числа, такую, что с предварительным просеиванием цикл можно сделать большими кусками.

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

time ./np 1000000000
allocated 119Mb
primes from 2 <= 1000000000 : 50847534

real    0m2.386s
user    0m2.354s
sys 0m0.032s

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

Подводя итог.Я хочу использовать предварительное просеивание.Я думаю, что это дает мне меньше сравнений плюс меньше внутренних циклов.Я спрашиваю вас, как записать простое число в другой форме, зная факт предварительного просеивания?

1 Ответ

0 голосов
/ 11 февраля 2019

Вы говорите, что, кроме 2 и 3, все простые числа имеют вид 2*3*k±1 (для некоторого целого числа k> = 1)

Вы можете расширить это до

2 * 3 * 5 * k ± {1, 7, 11, 13} (и 2, 3, 5, 7, 11, 13)

или

2 * 3 *5 * 7 * k ± {1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109} (и 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97)

Реализация этих форм может не сделать вашу программу более эффективной (однако вы определяете эффективность).Вам нужно измерить.

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

...