Explicação da peneira de Atkin
https://stackoverflow.com/questions/1023768
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Estou fazendo um projeto no momento e preciso de um método eficiente para calcular números primos.Eu usei o peneira de Eratóstenes mas, estive pesquisando e descobri que o peneira de Atkin é um método mais eficiente.Achei difícil encontrar uma explicação (que eu conseguisse entender!) Para esse método.Como funciona?Código de exemplo (de preferência em C ou python) seria brilhante.
Editar: obrigado pela ajuda, a única coisa que ainda não entendi é a que se referem as variáveis x e y no pseudocódigo.Alguém poderia, por favor, lançar alguma luz sobre isso para mim?
Solução
O página wiki é sempre um bom ponto de partida, pois explica o algoritmo por completo e fornece pseudocódigo comentado.(N. B.Há muitos detalhes e, como o site wiki é confiável, não vou citá-lo aqui.)
Para referências nos idiomas específicos que você mencionou:
- Implementação C (otimizado)
- Implementação Python
Espero que ajude.
Outras dicas
Artigo da Wikipédia tem uma explicação:
- "O algoritmo ignora completamente quaisquer números divisíveis por dois, três ou cinco.Todos os números com resto par módulo sessenta são divisíveis por dois e não são primos.Todos os números com resto módulo sessenta divisíveis por três também são divisíveis por três e não são primos.Todos os números com resto módulo sessenta divisíveis por cinco são divisíveis por cinco e não são primos.Todos esses restos são ignorados."
Vamos começar com o 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
Vamos ver como isso acontece nas primeiras etapas:
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 é não conter múltiplos de 2.IOW conterá apenas números primos com 2 - nenhum número em p2 tem 2 como seu fator.Encontrar p2 na verdade não precisamos testar a divisão por 2 cada número em [3..] (isso é 3 para cima, 3,4,5,6,7,...), porque podemos enumerar todos os múltiplos de 2 antecipadamente:
rem y 2 /= 0 === not (ordElem y [2,4..]) -- "y is not one of 2,4,6,8,10,..."
ordElem é como elem (ou seja, é-elemento teste), é apenas assume que seu argumento de lista é uma lista ordenada e crescente de números, para que possa detectar a não presença com segurança, bem como a presença:
ordElem y xs = take 1 (dropWhile (< y) xs) == [y] -- = elem y (takeWhile (<= y) xs)
O comum elem não assume nada, portanto deve inspecionar cada elemento de seu argumento de lista, portanto não pode lidar com listas infinitas. ordElem pode.Então,
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 é apenas uma lista de todas as probabilidades acima 2.Bem, nós sabíamos que.E o próximo 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 o próximo,
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 ]]
Esta é a sequência com a qual a peneira de Atkin funciona.Não há múltiplos de 2, 3 ou 5 estão presentes nele.Módulo de trabalho de Atkin e Bernstein 60, ou sejaeles dobram o alcance:
p60 = [ 60*k+x | k <- [0..], x <- [1, 7,11,13,17,19,23,29,31, 37,41,43,47,49,53,59]]
Em seguida, eles usam alguns teoremas sofisticados para conhecer algumas propriedades de cada um desses números e lidar com cada um de acordo.A coisa toda se repete (a-la a "roda") com um período de 60.
- "Todos os números n com módulo sessenta resto 1, 13, 17, 29, 37, 41, 49 ou 53 (...) são primos se e somente se o número de soluções para
4x^2 + y^2 = né ímpar e o número não tem quadrados."
O que isso significa?Se soubermos que o número de soluções dessa equação é ímpar para tal número, então ele é primo se é livre de quadrados.Isso significa que não há fatores repetidos (como 49, 121, etc).
Atkin e Bernstein usam isso para reduzir o número geral de operações:para cada primo (de 7 e acima), enumeramos (e marcamos para remoção) os múltiplos de seu quadrado, então eles estão muito mais distantes do que na peneira de Eratóstenes, então há menos deles em um determinado intervalo.
O resto das regras são:
"Todos os números n com módulo sessenta resto 7, 19, 31 ou 43 (...) são primos se e somente se o número de soluções para
3x^2 + y^2 = né ímpar e o número não tem quadrados.""Todos os números n com módulo sessenta resto 11, 23, 47 ou 59 (...) são primos se e somente se o número de soluções para
3x^2 − y^2 = né ímpar e o número não tem quadrados."
Isso cuida de todos os 16 números principais na definição de p60.
Veja também: Qual é o algoritmo mais rápido para encontrar números primos?
A complexidade temporal da peneira de Eratóstenes na produção de números primos até N é SOBRE log log N), enquanto o da peneira de Atkin é SOBRE) (deixando de lado o adicional log log N otimizações que não são bem dimensionadas).A sabedoria aceita, porém, é que os fatores constantes na peneira de Atkin são muito mais altos e, portanto, só podem render muito acima dos números de 32 bits (N > 232), se for o caso.
Editar:a única coisa que ainda não entendi é a que se referem as variáveis xey no pseudocódigo.Alguém poderia, por favor, lançar alguma luz sobre isso para mim?
Para uma explicação básica do uso comum das variáveis 'x' e 'y' no pseudocódigo da página da Wikipedia (ou outras implementações melhores do Sieve of Atkin), você pode encontrar minha resposta para outra pergunta relacionada útil.
Aqui está uma implementação em C++ do Sieve of Atkins que pode ajudá-lo...
#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;
}
