Spiegazione del setaccio di Atkin
https://stackoverflow.com/questions/1023768
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Al momento sto facendo un progetto e ho bisogno di un metodo efficiente per calcolare i numeri primi. Ho usato il setaccio di Eratosthenes ma ho cercato in giro e ho scoperto che setaccio di Atkin è un metodo più efficiente. Ho trovato difficile trovare una spiegazione (che ho potuto capire!) Di questo metodo. Come funziona? Il codice di esempio (preferibilmente in C o Python) sarebbe brillante.
Modifica: grazie per il tuo aiuto, l'unica cosa che ancora non capisco è a cosa si riferiscano le variabili xey nello pseudo codice. Qualcuno potrebbe far luce su questo per me?
Soluzione
La pagina wiki è sempre un buon punto di partenza, poiché spiega l'algoritmo in pieno e fornisce uno pseudocodice commentato. (N.B. Ci sono molti dettagli, e poiché il sito web della wiki è affidabile, non lo citerò qui.)
Per riferimenti nelle lingue specifiche menzionate:
- Implementazione in C (ottimizzato)
- Implementazione di Python
Spero che sia d'aiuto.
Altri suggerimenti
L'articolo di Wikipedia ha una spiegazione:
- " L'algoritmo ignora completamente qualsiasi numero divisibile per due, tre o cinque. Tutti i numeri con un resto pari a modulo-sessanta sono divisibili per due e non per primi. Tutti i numeri con resto modulo-sessanta divisibile per tre sono anche divisibili per tre e non primi. Tutti i numeri con resto modulo-sessanta divisibile per cinque sono divisibili per cinque e non primi. Tutti questi resti vengono ignorati. & Quot;
Cominciamo con il famoso
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
Vediamo come procede per alcuni primi passi:
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 non deve contenere multipli di 2 . IOW conterrà solo numeri coprimi con 2 & # 8212; nessun numero in p2 ha 2 come suo fattore. Per trovare p2 in realtà non è necessario testare la divisione per 2 ogni numero in [3 ..] (ovvero 3 e versioni successive, 3,4,5,6,7, ... ), perché possiamo elencare in anticipo tutti i multipli di 2 :
rem y 2 /= 0 === not (ordElem y [2,4..]) -- "y is not one of 2,4,6,8,10,..."
ordElem è come elem (ovvero is-element test), assume che il suo argomento dell'elenco sia un ordine, crescente elenco di numeri, in modo che possa rilevare in modo sicuro la non presenza e la presenza:
ordElem y xs = take 1 (dropWhile (< y) xs) == [y] -- = elem y (takeWhile (<= y) xs)
Il normale elem non assume nulla, quindi deve ispezionare ogni elemento del suo argomento list, quindi non può gestire elenchi infiniti. ordElem can. Quindi, quindi,
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 è solo un elenco di tutte le probabilità sopra 2 . Bene, sapevamo che . E il prossimo passo?
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,...
E il prossimo,
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 ]]
Questa è la sequenza con cui sta lavorando il setaccio di Atkin. Non sono presenti multipli di 2, 3 o 5 . Atkin e Bernstein lavorano modulo 60 , cioè raddoppiano la gamma:
p60 = [ 60*k+x | k <- [0..], x <- [1, 7,11,13,17,19,23,29,31, 37,41,43,47,49,53,59]]
Successivamente, usano alcuni teoremi sofisticati per conoscere alcune proprietà di ciascuno di quei numeri e gestirli di conseguenza. Il tutto viene ripetuto (come la "ruota") con un periodo di 60 .
- " Tutti i numeri n con resto modulo-sessanta 1, 13, 17, 29, 37, 41, 49 o 53 (...) sono primi se e solo se il numero di soluzioni per
4x ^ 2 + y ^ 2 = n è dispari e il numero è senza quadrati. & Quot;
Cosa significa? Se sappiamo che il numero di soluzioni a tale equazione è dispari per tale numero, allora è se primo è quadrato. Ciò significa che non ha fattori ripetuti (come 49, 121, ecc.).
Atkin e Bernstein lo usano per ridurre il numero complessivo di operazioni: per ogni numero primo (da 7 in su), enumeriamo (e contrassegniamo per la rimozione) i multipli di il suo quadrato , quindi sono molto più distanti rispetto al setaccio di Eratostene, quindi ce ne sono meno in un determinato intervallo.
Il resto delle regole sono:
" Tutti i numeri n con resto modulo-sessanta 7, 19, 31 o 43 (...) sono primi se e solo se il numero di soluzioni per
3x ^ 2 + y ^ 2 = nè dispari e il numero è senza quadrati. "" Tutti i numeri n con resto modulo-sessanta 11, 23, 47 o 59 (...) sono primi se e solo se il numero di soluzioni per
3x ^ 2 & # 8722; y ^ 2 = nè dispari e il numero è senza quadrati. "
Questo si occupa di tutti i 16 numeri core nella definizione di p60 .
vedi anche: Qual è l'algoritmo più veloce per trovare i numeri primi?
La complessità temporale del setaccio di Eratostene nella produzione di numeri primi fino a N è O (N log log N) , mentre quella del setaccio di Atkin è O (N) (mettendo da parte le ottimizzazioni aggiuntive log log N che non si adattano bene). La saggezza accettata è che i fattori costanti nel setaccio di Atkin sono molto più alti e quindi potrebbe ripagare solo al di sopra dei numeri a 32 bit ( N > 2 32 ) , se affatto .
Modifica: l'unica cosa che ancora non capisco è a cosa si riferiscano le variabili xey nello pseudo codice. Qualcuno potrebbe far luce su questo per me?
Per una spiegazione di base dell'uso comune delle variabili 'x' e 'y' nello pseudo-codice della pagina Wikipedia (o altre migliori implementazioni del setaccio di Atkin), potresti trovare la mia risposta a un'altra domanda correlata utile.
Ecco un'implementazione c ++ di setaccio di atkins che potrebbe aiutarti ...
#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;
}
