Sieb von Atkin Erklärung
https://stackoverflow.com/questions/1023768
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich mache momentan ein Projekt und brauche eine effiziente Methode zur Berechnung der Primzahlen. Ich habe das benutzt Sieb von Eratosthenes Aber ich habe herum gesucht und festgestellt, dass die Sieb von Atkin ist eine effizientere Methode. Ich habe es schwierig gefunden, eine Erklärung (die ich verstehen konnte!) Dieser Methode zu finden. Wie funktioniert es? Beispielcode (vorzugsweise in C oder Python) wäre brillant.
Bearbeiten: Vielen Dank für Ihre Hilfe. Das einzige, was ich immer noch nicht verstehe, ist, worauf sich die X- und Y -Variablen im Pseudocode beziehen. Könnte jemand bitte etwas Licht für mich werfen?
Lösung
Das Wiki -Seite ist immer ein guter Ausgangspunkt, da er den Algorithmus vollständig erklärt und kommentierte Pseudocode liefert. (NB Es gibt viele Details, und da die Wiki -Website zuverlässig stand, werde ich es hier nicht zitieren.)
Für Referenzen in den spezifischen Sprachen, die Sie erwähnt haben:
- C Implementierung (optimiert)
- Python -Implementierung
Ich hoffe, das hilft.
Andere Tipps
Wikipedia -Artikel hat eine Erklärung:
- "Der Algorithmus ignoriert alle Zahlen vollständig durch zwei, drei oder fünf. Alle Zahlen mit einem gleichmäßigen Modulo-Sechs-Rest sind durch zwei teilbar und nicht primär. Alle Zahlen mit modulo-oxty rest sind auch durch drei teilbar und nicht um drei und nicht um drei teilbar und nicht um drei und nicht. Prime. Alle Zahlen mit modulo-gixty Rest durch fünf sind durch fünf teilbar und nicht für Prime. Alle diese Reste werden ignoriert. "
Beginnen wir mit dem Berühmten
primes = sieve [2..] = sieve (2:[3..])
-- primes are sieve of list of 2,3,4... , i.e. 2 prepended to 3,4,5...
sieve (x:xs) = x : sieve [y | y <- xs, rem y x /= 0] -- set notation
-- sieve of list of (x prepended to xs) is x prepended to the sieve of
-- list of `y`s where y is drawn from xs and y % x /= 0
Mal sehen, wie es für ein paar erste Schritte verläuft:
primes = sieve [2..] = sieve (2:[3..])
= 2 : sieve p2 -- list starting w/ 2, the rest is (sieve p2)
p2 = [y | y <- [3..], rem y 2 /= 0] -- for y from 3 step 1: if y%2 /= 0: yield y
p2 ist keine Vielfachen von 2. Es wird nur Zahlen mit Coprime enthalten 2 - Keine Nummer in p2 hat 2 Als Faktor. Finden p2 Wir müssen die Kluft nicht durch 2 jede Zahl in [3..] (Das ist 3 und hoch, 3,4,5,6,7,...), weil wir alle Vielfachen aufzählen können 2 im Voraus:
rem y 2 /= 0 === not (ordElem y [2,4..]) -- "y is not one of 2,4,6,8,10,..."
ordElem ist wie elem (dh Is-Element Test), es nur geht davon aus Dass sein Listenargument eine geordnete, zunehmende Liste von Zahlen ist, sodass die Nichtverträglichkeit sowohl sicher als auch Präsenz erkennen kann:
ordElem y xs = take 1 (dropWhile (< y) xs) == [y] -- = elem y (takeWhile (<= y) xs)
Die Gewöhnlichen elem Nimmt nichts an, muss also jedes Element seines Listenarguments inspizieren, also kann es in unendlichen Listen nicht verarbeiten. ordElem kann. Also dann,
p2 = [y | y <- [3..], not (ordElem y [2,4..])] -- abstract this as a function, diff a b =
= diff [3..] [2,4..] -- = [y | y <- a, not (ordElem y b)]
-- 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
-- . 4 . 6 . 8 . 10 . 12 . 14 . 16 . 18 . 20 . 22 .
= diff [3..] (map (2*) [2..] ) -- y > 2, so [4,6..] is enough
= diff [2*k+x | k <- [0..], x <- [3,4]] -- "for k from 0 step 1: for x in [3,4]:
[2*k+x | k <- [0..], x <- [ 4]] -- yield (2*k+x)"
= [ 2*k+x | k <- [0..], x <- [3 ]] -- 2 = 1*2 = 2*1
= [3,5..] -- that's 3,5,7,9,11,...
p2 ist nur eine Liste aller oben genannten Gewinnchancen 2. Nun, wir wussten das. Was ist mit dem nächsten Schritt?
sieve p2 = sieve [3,5..] = sieve (3:[5,7..])
= 3 : sieve p3
p3 = [y | y <- [5,7..], rem y 3 /= 0]
= [y | y <- [5,7..], not (ordElem y [3,6..])] -- 3,6,9,12,...
= diff [5,7..] [6,9..] -- but, we've already removed the multiples of 2, (!)
-- 5 . 7 . 9 . 11 . 13 . 15 . 17 . 19 . 21 . 23 . 25 . 27 .
-- . 6 . . 9 . . 12 . . 15 . . 18 . . 21 . . 24 . . 27 .
= diff [5,7..] (map (3*) [3,5..]) -- so, [9,15..] is enough
= diff [2*k+x | k <- [0..], x <- [5]] (map (3*)
[2*k+x | k <- [0..], x <- [ 3]] )
= diff [6*k+x | k <- [0..], x <- [5,7,9]] -- 6 = 2*3 = 3*2
[6*k+x | k <- [0..], x <- [ 9]]
= [ 6*k+x | k <- [0..], x <- [5,7 ]] -- 5,7,11,13,17,19,...
Und der nächste,
sieve p3 = sieve (5 : [6*k+x | k <- [0..], x <- [7,11]])
= 5 : sieve p5
p5 = [y | y <- [6*k+x | k <- [0..], x <- [7,11]], rem y 5 /= 0]
= diff [ 6*k+x | k <- [0..], x <- [7,11]] (map (5*)
[ 6*k+x | k <- [0..], x <- [ 5, 7]]) -- no mults of 2 or 3!
= diff [30*k+x | k <- [0..], x <- [7,11,13,17,19,23,25,29,31,35]] -- 30 = 6*5 = 5*6
[30*k+x | k <- [0..], x <- [ 25, 35]]
= [ 30*k+x | k <- [0..], x <- [7,11,13,17,19,23, 29,31 ]]
Dies ist die Sequenz, mit der das Sieb von Atkin funktioniert. Keine Vielfachen von 2, 3 oder 5 sind darin vorhanden. Atkin und Bernstein Arbeitsmodulo 60, dh sie verdoppeln den Bereich:
p60 = [ 60*k+x | k <- [0..], x <- [1, 7,11,13,17,19,23,29,31, 37,41,43,47,49,53,59]]
Als nächstes verwenden sie einige anspruchsvolle Theoreme, um einige Eigenschaften jeder dieser Zahlen zu kennen und mit jedem entsprechend zu behandeln. Das Ganze wird wiederholt (a-la das "Rad") mit einer Zeit von 60.
- "Alle Zahlen n mit Modulo-Sechse-Rest 1, 13, 17, 29, 37, 41, 49 oder 53 (...) sind nur dann primär, wenn die Anzahl der Lösungen an Lösungen zu
4x^2 + y^2 = nist ungerade und die Zahl ist quadratisch frei. "
Was bedeutet das? Wenn wir wissen, dass die Anzahl der Lösungen für diese Gleichung für eine solche Zahl ungerade ist, dann ist es Primzahl wenn Es ist quadratfrei. Das heißt, es gibt keine wiederholten Faktoren (wie 49, 121, etc).
Atkin und Bernstein verwenden dies, um die Anzahl der Operationen insgesamt zu verringern: für jede Primzahl (von 7 und auf), wir zählen (und markieren sie zum Entfernen) die Vielfachen von sein Quadrat, Sie sind also viel weiter voneinander entfernt als im Sieb von Eratosthenes, so dass es weniger in einem bestimmten Bereich gibt.
Der Rest der Regeln ist:
"Alle Zahlen n mit modulo-oxty Rest 7, 19, 31 oder 43 (...) sind nur dann primär, wenn die Anzahl der Lösungen an Lösungen
3x^2 + y^2 = nist ungerade und die Zahl ist quadratisch frei. ""Alle Zahlen n mit Modulo-Sechse-Rest 11, 23, 47 oder 59 (...) sind nur dann primär, wenn die Anzahl der Lösungen an Lösungen
3x^2 − y^2 = nist ungerade und die Zahl ist quadratisch frei. "
Dies kümmert sich um alle 16 Kernzahlen in der Definition von p60.
siehe auch: Welches ist der schnellste Algorithmus, um Primzahlen zu finden?
Die zeitliche Komplexität des Siebs von Eratosthenen bei der Erzeugung von Primzahlen bis zu N ist O (N log log N), während das des Sieb von Atkin ist AN) (Abzüglich des zusätzlichen Platzes beiseite legen log log N Optimierungen, die nicht gut skalieren). Die akzeptierte Weisheit ist jedoch, dass die ständigen Faktoren im Sieb von Atkin viel höher sind und sich daher nur über die 32-Bit-Zahlen auszahlen ().N> 232), wenn überhaupt.
Bearbeiten: Das einzige, was ich immer noch nicht verstehe, ist, worauf die X- und Y -Variablen im Pseudocode beziehen. Könnte jemand bitte etwas Licht für mich werfen?
Für eine grundlegende Erläuterung der gemeinsamen Verwendung der "X" und "Y" -Variablen in der Wikipedia-Seite Pseudo-Code (oder andere bessere Implementierungen des Sieb von Atkin) könnten Sie finden Meine Antwort auf eine andere verwandte Frage hilfreich.
Hier ist eine C ++ - Implementierung von Sieb von Atkins, die Ihnen helfen könnten ...
#include <iostream>
#include <cmath>
#include <fstream>
#include<stdio.h>
#include<conio.h>
using namespace std;
#define limit 1000000
int root = (int)ceil(sqrt(limit));
bool sieve[limit];
int primes[(limit/2)+1];
int main (int argc, char* argv[])
{
//Create the various different variables required
FILE *fp=fopen("primes.txt","w");
int insert = 2;
primes[0] = 2;
primes[1] = 3;
for (int z = 0; z < limit; z++) sieve[z] = false; //Not all compilers have false as the default boolean value
for (int x = 1; x <= root; x++)
{
for (int y = 1; y <= root; y++)
{
//Main part of Sieve of Atkin
int n = (4*x*x)+(y*y);
if (n <= limit && (n % 12 == 1 || n % 12 == 5)) sieve[n] ^= true;
n = (3*x*x)+(y*y);
if (n <= limit && n % 12 == 7) sieve[n] ^= true;
n = (3*x*x)-(y*y);
if (x > y && n <= limit && n % 12 == 11) sieve[n] ^= true;
}
}
//Mark all multiples of squares as non-prime
for (int r = 5; r <= root; r++) if (sieve[r]) for (int i = r*r; i < limit; i += r*r) sieve[i] = false;
//Add into prime array
for (int a = 5; a < limit; a++)
{
if (sieve[a])
{
primes[insert] = a;
insert++;
}
}
//The following code just writes the array to a file
for(int i=0;i<1000;i++){
fprintf(fp,"%d",primes[i]);
fprintf(fp,", ");
}
return 0;
}
// Title : Seive of Atkin ( Prime number Generator)
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
long long int n;
cout<<"Enter the value of n : ";
cin>>n;
vector<bool> is_prime(n+1);
for(long long int i = 5; i <= n; i++)
{
is_prime[i] = false;
}
long long int lim = ceil(sqrt(n));
for(long long int x = 1; x <= lim; x++)
{
for(long long int y = 1; y <= lim; y++)
{
long long int num = (4*x*x+y*y);
if(num <= n && (num % 12 == 1 || num%12 == 5))
{
is_prime[num] = true;
}
num = (3*x*x + y*y);
if(num <= n && (num % 12 == 7))
{
is_prime[num] = true;
}
if(x > y)
{
num = (3*x*x - y*y);
if(num <= n && (num % 12 == 11))
{
is_prime[num] = true;
}
}
}
}
// Eliminating the composite by seiveing
for(long long int i = 5; i <= lim; i++)
{
if(is_prime[i])
for(long long int j = i*i; j <= n; j += i)
{
is_prime[j] = false;
}
}
// Here we will start printing of prime number
if(n > 2)
{
cout<<"2\t"<<"3\t";
}
for(long long int i = 5; i <= n; i++)
{
if(is_prime[i])
{
cout<<i<<"\t";
}
}
cout<<"\n";
return 0;
}
