В начало

Решето Эратосфена

Понадобилась мне быстрая работа с небольшими простыми числами (до нескольких миллиардов). Естественный алгоритм - решето Эратосфена. Есть его хорошие реализации, но как часть больших и сложных проектов. Включить их в свою программу не так просто. Оказалось проще написать свою версию.

В решете хранятся только нечетные числа, по одному биту на каждое. Поэтому N байтов достаточно для храненения простых чисел до 16*N+1. То есть для хранения всех простых до 1 млн. требуется 63К байт. В одном гигабайте помещаются простые числа до 16 миллиардов.

Предлагается простая и эффективная реализация решета Эратосфена - способа перечисления всех простых чисел до заданной границы. Реализация состоит из двух файлов:
Eratosthenes.h - заголовочный файл
Eratosthenes.cpp - реализация.

Заголовочный файл устроен так: 

typedef __int64	INT64;   // For Visual C++, change this definition for other compilers

void  Sieve_fill(INT64 maxN);   // fill sieve for primes till maxN
void  Sieve_free();             // free memory
INT64 Sieve_Size();             // return size in BYTES!
INT64 Sieve_maxN();             // return maximal N
bool  Sieve_isPrime( INT64 n);  // is prime(n)?
int   Sieve_save(char *fname);  // returns error code
int   Sieve_load(char *fname);  // returns error code
Все простые числа до 4 млрд. получены за 72 сек (AMD Athlon II X2 240, 2.8 GHz). То же самое с заменой __int64 на unsigned сделано за 52 сек., Разница небольшая, не стоит стараться. На процессоре Intel Atom 1.66 GHz это же вычисление занимает 163 сек (вместо 72).

Время заполнения решета на процессоре AMD Athlon II X2 240, 2.8 GHz

N max 106 107 224 108 228 229 109 231 232 233 234
time, sec 0.056 0.064 0.11 1.3 3.9 8.3 16.2 37 72 155 326

Вот основная, рабочая функция проверки числа на простоту: 

bool  Sieve_isPrime( INT64 n)	// is prime(n)?
{
	INT64 y = (n>>1)-1;
	unsigned x8 = (unsigned)(y>>3);
	if( x8>=size ) return true;
	unsigned x3 = (unsigned)(y &7);
	return  (v[x8]&(1< 0? 1 : 0;
}

Использование пакета: 

#include "Eratosthenes.h"
...
    Sieve_fill(1000000);        // create list of primes till one mill.
    ...
    if( Sieve_isPrime(700001) ) {...} // check primularity
    ...
    Sieve_free();
Настройка пакета на различные процессоры и компиляторы сводится к корректировке строки в заголовочном файле: 
typedef __int64	INT64;   // For Visual C++, change this definition for other compilers
В ней надо указать название типа 64-битовых целых чисел.

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

Если запрашиваемое на проверку простоты число превышает размеры таблицы, то оно считается составным, ошибка не происходит. Поэтому заранее проверяйте максимально допустимое число для проверки: 

INT64 Sieve_maxN();


free counters