Primzahl Suchalgorithmus (zwei verschiedene Algorithmen) und Verwendung von Primzahl-Tabellen - C ++, C, Algorithmus, mathematische Optimierung

Ich habe zwei Algorithmen geschrieben, um Primzahlen zu finden. isPrime() - basiert auf der Suche nach ungeraden Divisoren von 3 bis zur Quadratwurzel der zu analysierenden ungeraden Zahlen (die geraden Zahlen werden verworfen), die zweite - isPrime2() - basiert auf der Annahme, dass alle PrimzahlenZahlen größer als 3 haben die Form: p = k * 6-1 oder p = k * 6 + 1. (Diese Funktion betrachtet die Zahl 1 als eine Primzahl, aber es ist einfach, dieses Verhalten zu ändern, wenn Sie denken, dass 1 keine Primzahl ist!)

Der zweite Algorithmus ist etwas schneller als der erste, aber mit Tabellen haben sie mindestens die gleiche Geschwindigkeit.

Durch die Verwendung von Tabellen (wie die main (), unten) wird die Suche zweimal schneller (Suche nach der ersten Million Primzahlen) als ohne sie zu verwenden. Sie können diese Tatsache überprüfen, indem Sie die Anrufe an die isPrime() Funktionen in der while Schleifen wie im Folgenden:

isPrime(n, NULL);

Anstatt von:

isPrime(n, &tbl[x]);

Die main () lädt zwei Primzahl-Tabellen, die eine Million Primzahlen enthalten, wobei eine Primzahl verwendet wird isPrime() und der andere benutzt isPrime2(), dann die verwendete Zeit und einige Primzahlen ausdrucken. Danach vergleicht main () die Ergebnisse der beiden Tabellen.

Ich interessiere mich für Algorithmen, um Prime zu füllenZahlen Tabellen (auch von 1) und zu identifizieren, ob eine große / große Zahl eine Primzahl ist. Hast du Vorschläge? Kennen Sie unterschiedliche oder schnellere Algorithmen?

#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;
}

Antworten:

Abhängig von den Eingabewerten, aber wenn Sie effizienter werden wollen, verwendet eine bekannte Lösung die Sieb von Eratosthenes.

Das Sieb ähnelt dem Konzept "check ob es einen ungeraden Divisor gibt" - warum nur Quoten? Weil nur gerade Primzahl 2 ist. Ähnlich könnte man es für 3,5 und jede andere Primzahl machen.
Das Sieb findet diese Primzahl dynamisch und verwirft alle Nicht-Primzahlen, die von jeder Primzahl beeinflusst werden.

Wenn Sie nach einer einzigen großen Überprüfung suchennumber ist prim, es gibt tatsächlich eine effiziente Lösung, die in polynomieller Zeit die Anzahl der Bits, die die Zahl (Polynom des Logarithmus der Zahl) darstellen, ausführt AKS