mar*_*oln 21 primes sieve-of-eratosthenes sieve-of-atkin
我正在做一个项目,我需要一种有效的方法来计算素数.我使用了Eratosthenes的筛子,但是我一直在寻找并发现Atkin的筛子是一种更有效的方法.我发现很难找到这种方法的解释(我能够理解!).它是如何工作的？示例代码(最好是在C或python中)很棒.
编辑:感谢您的帮助,我唯一不理解的是x和y变量在伪代码中引用的内容.有人可以帮我解释一下吗？
Wil*_*ess 10
维基百科的文章有一个解释:
让我们从着名的开始吧
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的数字coprime - 没有数字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(即元素测试)一样,它只是假设它的列表参数是一个有序的,增加的数字列表,因此它可以安全地检测不存在以及存在:
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,即他们的范围加倍:
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 the"wheel"),周期为60.
4x^2 + y^2 = n为奇数且数字为无平方时,所有具有模数为60的余数1,13,17,29,37,41,49 或53(...)的数字n都是素数."那是什么意思？如果我们知道该等式的解的数量对于这样的数字是奇数,那么如果它是无平方的则它是素数.这意味着它没有重复的因素(如49,121等).
Atkin和Bernstein使用它来减少整体操作的数量:对于每个素数(从7和更高),我们枚举(并标记为移除)其平方的倍数,因此它们比Eratosthenes的筛子远得多,所以在给定范围内它们更少.
其余规则是:
"当且仅当解决方案的数量3x^2 + y^2 = n为奇数且数字为无平方时,所有具有模数为60的余数7,19,31 或43(...)的数字n都是素数."
"当且仅当解决方案的数量3x^2 ? y^2 = n为奇数且数字为无平方时,所有具有模数为60的余数11,23,47 或59(...)的数字n都是素数."
这将处理定义中的所有16个核心数字p60.
另请参阅:找到素数的最快算法是哪一种？
Eratosthenes筛子在生产N中的质数时间复杂度为O(N log log N),而Atkin 筛子的时间复杂度为O(N)(撇开log log N不能很好地扩展的额外优化).然而,公认的智慧是阿特金筛子中的常数因子要高得多,所以它可能只会高于32位数(N> 2 32),如果有的话.