Algorytm wyszukiwania liczb pierwszych (dwa różne algorytmy) i wykorzystanie tabel pierwszorzędnych - c ++, c, algorytm, optymalizacja matematyczna

Napisałem dwa algorytmy, aby znaleźć liczby pierwsze. isPrime() - polega na wyszukiwaniu nieparzystych dzielników od 3 do pierwiastka kwadratowego liczb nieparzystych do zanalizowania (liczby parzyste są odrzucane), a drugi - isPrime2() - opiera się na założeniu, że wszystkie primeliczby większe niż 3 mają postać: p = k * 6-1 lub p = k * 6 + 1. (Funkcja ta uważa, że ​​liczba 1 jest liczbą pierwszą, ale można łatwo zmienić to zachowanie, jeśli uważasz, że 1 nie jest liczbą pierwszą!)

Drugi algorytm jest nieco szybszy od pierwszego, ale przy użyciu tabel ma co najmniej taką samą prędkość.

Używając tabel (jako główne (), poniżej, nie) wyszukiwanie staje się dwa razy szybsze (wyszukiwanie pierwszego miliona liczb pierwszych) niż bez ich użycia. Możesz zweryfikować ten fakt modyfikując połączenia do isPrime() funkcje w while pętle jak poniżej:

isPrime(n, NULL);

zamiast:

isPrime(n, &tbl[x]);

Funkcja main () ładuje dwie tabele liczb pierwszych zawierające milion liczb pierwszych, z których jedna używa isPrime() a drugi używa isPrime2(), następnie wydrukuj używany czas i kilka liczb pierwszych. Następnie main () porównuje wyniki dwóch tabel.

Interesuję się algorytmami wypełniania primetabele liczb (również zaczynające się od 1) i wskazanie, czy duża / ogromna liczba jest liczbą pierwszą. Czy masz sugestie? Czy znasz inne lub szybsze algorytmy?

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <math.h>
#include <sys/time.h>

typedef struct prime_table {
uint64_t * primes;
uint32_t inTable;
uint32_t maxIn;
} table;

int isPrime(uint64_t n, table * t)
{
uint64_t i, k, m;

if(!n)
return 0;

if(n < 4)
return 1;

if(!(n & 1))    /* the number is even */
return 0;

m = sqrt(n);

k = 1;
if(t) {
for(i = 2; i < t->inTable && t->primes[i] <= m; i++) {
k = t->primes[i];
if(!(n % k))
return 0;
}
}

k += 2;
for(i = k; i <= m; i += 2) {
if(!(n % i))
return 0;
}

return 1;
}

int isPrime2(uint64_t n, table * t)
{
uint64_t i, k, m;

if(!n)
return 0;

if(n < 4 || n == 5)
return 1;

if(!(n & 1))    /* the number is even */
return 0;

if(!(n % 3))
return 0;

k = (n - 1) / 6; m = (n + 1) / 6;
if(k * 6 + 1 != n && m * 6 - 1 != n)
return 0;

m = sqrt(n);
k = 5;
if(t) {
for(i = 3; i < t->inTable && t->primes[i] <= m; i++) {
k = t->primes[i];

if(!(n % k))
return 0;
}
}
k += 2;

k = (k - 1) / 6; m = (m + 1) / 6;
for(i = k; i <= m; i++) {
if(!(n % (6 * i - 1)) || !(n % (6 * i + 1)))
return 0;
}

return 1;
}

uint32_t getusec()
{
struct timeval t;
gettimeofday(&t, NULL);

return (t.tv_sec * 1000000UL + t.tv_usec);
}

int main(void)
{
static table tbl[2];
uint64_t n = 1;
uint32_t t, i, j;

/* Init two prime tables */
for(i = 0; i < 2; i++) {
tbl[i].maxIn = 1000000;
tbl[i].primes = malloc(tbl[i].maxIn * sizeof(*tbl[0].primes));

/* Load the 1,2 and 3 into the table */
for(j = 1; j < 4; j++)
tbl[i].primes[j - 1] = j;

tbl[i].inTable = 3;
}

/* Loading table with isPrime()*/
t = getusec();
n = 3;
while(tbl[0].inTable < tbl[0].maxIn) {
n += 2;
if(isPrime(n, &tbl[0])) {
tbl[0].primes[tbl[0].inTable++] = n;
}
}

printf("%u primes computed in %u usecn", tbl[0].inTable, getusec() - t);
puts("First 16 computed primes");

for(i = 0; i < 16; i++)
printf("%9lu ", tbl[0].primes[i]);

puts("n--------------------");
puts("Last 16 computed primes");

for(i = tbl[0].inTable - 16; i < tbl[0].inTable; i++)
printf("%9lu ", tbl[0].primes[i]);

puts("n--------------------");

/* Loading table with isPrime2()*/
t = getusec();
n = 3;
while(tbl[1].inTable < tbl[1].maxIn) {
n += 2;
if(isPrime2(n, &tbl[1])) {
tbl[1].primes[tbl[1].inTable++] = n;
}
}

printf("%u primes computed in %u usecn", tbl[1].inTable, getusec() - t);
puts("First 16 computed primes");

for(i = 0; i < 16; i++)
printf("%9lu ", tbl[1].primes[i]);

puts("n--------------------");
puts("Last 16 computed primes");

for(i = tbl[1].inTable - 16; i < tbl[1].inTable; i++)
printf("%9lu ", tbl[1].primes[i]);

puts("n--------------------");
puts("Searching for differences in tables");

for(i = 0; i < tbl[0].inTable; i++) {
if(tbl[0].primes[i] != tbl[1].primes[i]) {
printf("%u %lu %lu", i, tbl[0].primes[i], tbl[1].primes[i]);
break;
}
}

if(i == tbl[0].inTable) {
puts("No differences have been found!");
}

puts("--------------------");
return 0;
}

Odpowiedzi:

W zależności od wartości wejściowych, ale jeśli chcesz uzyskać większą wydajność, znanym rozwiązaniem jest użycie Sito Eratostenesa.

Sito jest podobne do pojęcia "sprawdź, czy istnieje dziwny dzielnik" - dlaczego tylko szanse? Bo tylko prime to 2. Podobnie można to zrobić dla 3,5 i każdej innej liczby pierwszej.
Sito znajduje te prime dynamicznie i odrzuca wszystkie nie-pierwsze liczby, na które ma wpływ każda liczba pierwsza.

Jeśli szukasz sprawdzenia, czy jeden ogromnyliczba jest liczbą pierwszą, w rzeczywistości jest to skuteczne rozwiązanie, które działa w czasie wielomianu liczby bitów reprezentujących liczbę (wielomian logu liczby), który jest znany jako AKS