-
06-07-2019 - |
其他提示
维基百科文章 有一个解释:
- “该算法完全忽略任何能被二、三或五整除的数字。所有具有偶数模六十余数的数字都可以被二整除,并且不是素数。所有模六十余数可被三整除的数字也可被三整除,但不是素数。所有模六十余数可被五整除的数字都可被五整除,但不是素数。所有这些剩余部分都被忽略。”
我们先从著名的开始
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
让我们看看它是如何进行最初的几个步骤的:
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
是不包含的倍数 2. 。IOW 它只会包含与之互质的数字 2 — 没有数字 p2
有 2 作为其因素。寻找 p2
我们实际上不需要测试除以 2 中的每个数字 [3..]
(那是 3 向上, 3,4,5,6,7,...),因为我们可以枚举所有的倍数 2 提前:
rem y 2 /= 0 === not (ordElem y [2,4..]) -- "y is not one of 2,4,6,8,10,..."
ordElem
就好像 elem
(IE。 是元素 测试),它只是 假设 它的列表参数是一个有序的、递增的数字列表,因此它可以安全地检测不存在以及存在:
ordElem y xs = take 1 (dropWhile (< y) xs) == [y] -- = elem y (takeWhile (<= y) xs)
普通的 elem
不假设任何内容,因此必须检查其列表参数的每个元素,因此无法处理无限列表。 ordElem
能。那么,那么,
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
只是上面所有赔率的列表 2. 。嗯,我们知道 那. 。下一步怎么办?
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,...
接下来,
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 ]]
这就是阿特金筛的工作顺序。没有倍数 2, 3 或者 5 都存在于其中。阿特金和伯恩斯坦的模数工作 60, , IE。他们将范围加倍:
p60 = [ 60*k+x | k <- [0..], x <- [1, 7,11,13,17,19,23,29,31, 37,41,43,47,49,53,59]]
接下来,他们使用一些复杂的定理来了解每个数字的一些属性,并相应地处理每个数字。整个事情会重复(a-la“轮子”)一段时间 60.
- “所有具有模六十余数 1、13、17、29、37、41、49 或 53 (...) 的数字 n 都是素数当且仅当解的数量为
4x^2 + y^2 = n
是奇数并且该数是无方的。”
这意味着什么?如果我们知道对于这样的数字,该方程的解的数量是奇数,那么它是素数 如果 它是无正方形的。这意味着它没有重复因素(例如 49, 121, ETC)。
阿特金和伯恩斯坦使用它来减少总体操作数量:对于每个质数(从 7 及以上),我们枚举(并标记为删除)的倍数 它的正方形, ,所以它们比埃拉托斯特尼筛中的距离远得多,所以给定范围内的它们更少。
其余规则是:
“所有具有模六十余数 7、19、31 或 43 (...) 的数字 n 都是素数当且仅当解的数量为
3x^2 + y^2 = n
是奇数并且该数是无方的。”“所有具有模 60 余数 11、23、47 或 59 (...) 的数字 n 都是素数当且仅当解的数量为
3x^2 − y^2 = n
是奇数并且该数是无方的。”
这照顾了定义中的所有 16 个核心数字 p60
.
也可以看看: 哪种算法是查找素数最快的算法?
埃拉托色尼筛产生素数的时间复杂度高达 氮 是 O(N 对数 N), ,而阿特金筛则是 在) (抛开额外的 log log N
无法很好扩展的优化)。不过,公认的观点是阿特金筛中的常数因子要高得多,因此它可能只能在高于 32 位数字的情况下获得回报(数 > 232), 如果有的话.
编辑:我唯一不理解的是x和y变量在伪代码中引用的内容。有人可以帮我解释一下吗?
有关维基百科页面伪代码(或Atkin的Sieve的其他更好实现)中常见使用'x'和'y'变量的基本解释,您可能会发现我对其他相关问题的回答很有帮助。
这是一个可以帮助你的atkins筛子的c ++实现......
#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;
}