Atkin의 체 설명
https://stackoverflow.com/questions/1023768
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
저는 지금 프로젝트를 진행하고 있는데 소수를 계산하는 효율적인 방법이 필요합니다.나는 에라토스테네스의 체 그런데 여기저기 찾아보다가 알게 된 사실은 앳킨의 체 더 효율적인 방법입니다.나는 이 방법에 대한 설명(내가 이해할 수 있었던!)을 찾는 것이 어렵다는 것을 알았습니다.어떻게 작동하나요?예제 코드(바람직하게는 C 또는 Python)는 훌륭할 것입니다.
편집하다: 도움을 주셔서 감사합니다. 제가 아직도 이해하지 못하는 유일한 것은 의사 코드에서 x 및 y 변수가 참조하는 내용입니다.누군가 나에게 이것에 대해 좀 알려줄 수 있습니까?
다른 팁
위키피디아 기사 설명이 있습니다:
- "알고리즘은 2, 3, 5로 나눌 수 있는 모든 숫자를 완전히 무시합니다.나머지가 짝수인 모듈로 60을 갖는 모든 숫자는 소수가 아닌 2로 나눌 수 있습니다.모듈로 60의 나머지가 3으로 나누어지는 모든 숫자는 소수가 아닌 3으로도 나누어집니다.모듈로 60 나머지가 5로 나누어지는 모든 숫자는 5로 나누어지며 소수가 아닙니다.나머지는 모두 무시됩니다."
유명한 것부터 시작해보자
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 (즉. is-요소 테스트), 그냥 가정하다 목록 인수는 순서대로 증가하는 숫자 목록이므로 존재 여부뿐만 아니라 존재 여부도 안전하게 감지할 수 있습니다.
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 ]]
이것은 Atkin의 체(sieve of Atkin)가 작동하는 순서입니다.배수 없음 2, 3 또는 5 그 안에 존재합니다.Atkin과 Bernstein은 모듈로 작업을 수행합니다. 60, 즉.범위가 두 배로 늘어납니다.
p60 = [ 60*k+x | k <- [0..], x <- [1, 7,11,13,17,19,23,29,31, 37,41,43,47,49,53,59]]
다음으로, 그들은 각 숫자의 일부 속성을 파악하고 그에 따라 각각을 처리하기 위해 몇 가지 정교한 정리를 사용합니다.모든 것이 다음 기간 동안 반복됩니다("바퀴"라고도 함). 60.
- "모듈로 60 나머지가 1, 13, 17, 29, 37, 41, 49 또는 53(...)인 모든 숫자 n은 소수입니다.
4x^2 + y^2 = n홀수이고 숫자는 정사각형이 아닙니다."
그게 무슨 뜻이에요?해당 방정식에 대한 해의 개수가 홀수라는 것을 안다면, 그 숫자는 소수입니다. 만약에 그것은 스퀘어 프리입니다.이는 반복되는 요인이 없음을 의미합니다(예: 49, 121, 등).
Atkin과 Bernstein은 이를 사용하여 전반적인 작업 수를 줄입니다.각 소수에 대해 (부터 7 이상), 우리는 다음의 배수를 열거하고 제거 표시를 합니다. 그 광장, 따라서 그들은 에라토스테네스의 체보다 훨씬 더 멀리 떨어져 있으므로 주어진 범위에 더 적은 수가 있습니다.
나머지 규칙은 다음과 같습니다.
"모듈로 60 나머지가 7, 19, 31 또는 43(...)인 모든 숫자 n은 소수입니다.
3x^2 + y^2 = n홀수이고 숫자는 정사각형이 아닙니다.""모듈로 60 나머지가 11, 23, 47 또는 59(...)인 모든 숫자 n은 소수입니다.
3x^2 − y^2 = n홀수이고 숫자는 정사각형이 아닙니다."
이는 정의의 16개 핵심 숫자를 모두 처리합니다. p60.
또한보십시오: 소수를 찾는 가장 빠른 알고리즘은 무엇입니까?
소수를 생성하는 에라토스테네스 체의 시간복잡도 N ~이다 O(N 로그 로그 N), Atkin 체의 체는 에) (추가적인 내용은 제쳐두고 log log N 확장이 잘 안되는 최적화).그러나 받아들여지는 통념은 Atkin 체의 상수 요소가 훨씬 높기 때문에 32비트 숫자 이상에서만 높은 성과를 거둘 수 있다는 것입니다(아니오 > 232), 만약에 전혀.
편집 : 내가 여전히 이해하지 못하는 유일한 것은 X와 Y 변수가 의사 코드에서 참조하는 것입니다. 누군가 나를 위해 이것에 대해 약간의 빛을 비추어 줄 수 있습니까?
Wikipedia Page Pseudo-Code (또는 Atkin의 체의 다른 더 나은 구현)에서 '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;
}
