私は現在プロジェクトを行っており、素数を計算するための効率的な方法が必要です。私はエラトステネスのふるいを使ったことがありますが、いろいろと調べてみたところ、アトキンのふるいの方が効率的であることがわかりました。この方法の説明 (私は理解できました!) を見つけるのが難しいことがわかりました。それはどのように機能しますか？サンプル コード (できれば C または python) はすばらしいでしょう。
編集:ご協力ありがとうございます。私がまだ理解していないのは、疑似コードで x 変数と y 変数が参照しているものだけです。誰かが私のためにこれに光を当てることができますか?
ウィキペディアの記事には説明があります：
有名なものから始めましょう
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
p22の倍数を含まないことです。IOW には 2 と互いに素な数のみが含まれます—因数として2p2を持つ数はありません。事前にすべての2の倍数を列挙できるため、各数値( 3以上、3、4、5、6、7、... ) の2による除算を実際にテストする必要はありません。p2[3..]
rem y 2 /= 0 === not (ordElem y [2,4..]) -- "y is not one of 2,4,6,8,10,..."
ordElemのようにelem(つまりis-elementテスト)、そのリスト引数が番号の順序付けられた増加するリストであると想定しているだけなので、存在だけでなく非存在も安全に検出できます。
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の倍数は存在しません。Atkin と Bernstein は modulo 60で動作します。つまり、範囲を 2 倍にします。
p60 = [ 60*k+x | k <- [0..], x <- [1, 7,11,13,17,19,23,29,31, 37,41,43,47,49,53,59]]
次に、彼らはいくつかの洗練された定理を使用して、これらの各数値のいくつかのプロパティを知り、それに応じてそれぞれを処理します。全体が60の周期で繰り返されます (「ホイール」のように) 。
4x^2 + y^2 = nが奇数で、その数が平方自由である場合にのみ、素数です。」どういう意味ですか？その方程式の解の数がそのような数に対して奇数であることがわかっている場合、それが無平方であれば素数です。つまり、繰り返される要素 ( 49、121など) がないことを意味します。
Atkin と Bernstein は、これを使用して全体的な操作の数を減らしています: 各素数 ( 7以上) について、その平方の倍数を列挙 (および削除のためにマーク) するため、それらはエラトステネスのふるいよりもはるかに離れています。そのため、特定の範囲内にそれらの数が少なくなります。
残りのルールは次のとおりです。
3x^2 + y^2 = n「モジュロ 60 の剰余7、19、31、または 43 (...) を持つすべての数値 n は、 の解の数が奇数で、その数が平方自由である場合にのみ、素数です。」
3x^2 − y^2 = n「モジュロ 60 の剰余11、23、47、または 59 (...) を持つすべての数値 n は、 の解の数が奇数で、その数が平方自由である場合にのみ、素数です。」
これにより、 の定義に含まれる 16 個のコア番号すべてが処理されますp60。
Nまでの素数を生成する際のエラトステネスのふるいの時間計算量はO(N log log N)ですが、アトキンのふるいの時間計算量はO(N)log log Nです (うまくスケーリングしない追加の最適化は別として)。しかし、受け入れられている知恵は、Atkin のふるいの定数係数ははるかに高いため、32 ビット数 ( N > 2 32 )を超えた場合にのみ報われる可能性があるということです。
編集:私がまだ理解していない唯一のことは、疑似コードで x 変数と y 変数が参照しているものです。誰かが私のためにこれに光を当てることができますか?
ウィキペディア ページの疑似コード (またはアトキンのふるいの他のより良い実装) での「x」変数と「y」変数の一般的な使用方法の基本的な説明については、別の関連する質問に対する私の回答が役立つかもしれません。
これは、あなたを助けるかもしれないアトキンスのふるいの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;
}