غربال آتكن تفسير
https://stackoverflow.com/questions/1023768
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
وأنا أفعل المشروع في هذه اللحظة وأنا بحاجة إلى وسيلة فعالة لحساب الأعداد الأولية.لقد استخدمت غربال إراتوستينس ولكن لقد تم البحث حولها و وجدت أن غربال آتكن هو طريقة أكثر فعالية.لقد وجدت أنه من الصعب أن تجد تفسيرا (أن كنت قادرا على فهم!) هذا الأسلوب.كيف يعمل ؟ رمز المثال (يفضل أن يكون في C أو الثعبان) ستكون رائعة.
تحرير: شكرا على مساعدتك, الشيء الوحيد الذي ما زلت لا أفهم ما هو x و y المتغيرات إشارة إلى البرمجية الزائفة.يمكن للشخص يرجى إلقاء بعض الضوء على هذا بالنسبة لي ؟
المحلول
على صفحة ويكي هو دائما مكان جيد للبدء ، لأنه يوضح خوارزمية كاملة ويوفر علق شبة الكود.(N. B.هناك الكثير من التفاصيل و منذ ويكي الموقع موثوق لن أقتبس هنا.)
للحصول على مراجع في لغات معينة ذكرتها:
- ج التنفيذ (محسن)
- تنفيذ الثعبان
على أمل أن يساعد.
نصائح أخرى
مقالة ويكيبيديا وقد شرح:
- "خوارزمية يتجاهل تماما أي عدد يقبل القسمة على اثنين أو ثلاثة أو خمسة.جميع الأرقام حتى مودولو وستين تبقى هي القسمة على اثنين ولا رئيس الوزراء.جميع الأرقام مع مودولو وستين باقي القسمة على ثلاثة أيضا يقبل القسمة على ثلاثة وليس رئيس الوزراء.جميع الأرقام مع مودولو وستين باقي القسمة على خمسة القسمة على خمسة وليس رئيس الوزراء.كل هذه بقايا يتم تجاهلها."
دعونا نبدأ مع شهرة
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 إلا أنها سوف تحتوي على أرقام coprime مع 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 (أي هو عنصر اختبار) ، فإنه فقط يفترض أن قائمة الحجة هو أمر زيادة قائمة من الأرقام ، لذلك فإنه يمكن الكشف عن عدم وجود بأمان وكذلك وجود:
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 "عجلة") مع فترة 60.
- "كل الأرقام ن مع مودولو والستين المتبقية 1, 13, 17, 29, 37, 41, 49, أو 53 (...) رئيس الوزراء إذا و فقط إذا كان عدد من الحلول
4x^2 + y^2 = nهو غريب و عدد squarefree."
ماذا يعني ذلك ؟ إذا علمنا أن عدد حلول المعادلة هي غريبة على مثل هذا العدد ، ثم هو رئيس الوزراء إذا فمن squarefree.وهذا يعني أنه قد لا تتكرر العوامل (مثل 49, 121, وما إلى ذلك).
لآتكن و بيرنشتاين استخدام هذا إلى تقليل عدد العمليات الشاملة:لكل رئيس الوزراء (من 7 و متابعة) ، ونحن نعدد (و علامة إزالة) من مضاعفات مربع, لذا فهي أبعد من ذلك بكثير بعيدا في غربال إراتوستينس ، لذلك هناك عدد أقل منهم في نطاق معين.
بقية القواعد هي:
"كل الأرقام ن مع مودولو وستين تبقى 7, 19, 31, أو 43 (...) رئيس الوزراء إذا و فقط إذا كان عدد من الحلول
3x^2 + y^2 = nهو غريب و عدد squarefree.""كل الأرقام ن مع مودولو وستين تبقى 11, 23, 47, أو 59 (...) رئيس الوزراء إذا و فقط إذا كان عدد من الحلول
3x^2 − y^2 = nهو غريب و عدد squarefree."
هذا يأخذ الرعاية من كل 16 الأرقام الأساسية في تعريف p60.
انظر أيضا: الذي هو أسرع من خوارزمية لإيجاد الأعداد الأولية?
الوقت تعقيد غربال إراتوستينس في إنتاج يعبي تصل إلى N هو O(N log log N), في حين غربال من آتكن هو O(N) (نضع جانبا إضافية log log N التحسينات التي لا مقياس جيد).الحكمة المقبولة على الرغم من أن عوامل ثابتة في غربال من آتكن هي أعلى من ذلك بكثير و لذلك قد تدفع فقط من أعلى أرقام 32 بت (ن > 232), على كل حال.
وتحرير: الشيء الوحيد الذي ما زلت لا أفهم ما هو x و المتغيرات ص يحيلان إليه في رمز زائف. هل يمكن لشخص يرجى تسليط بعض الضوء على هذا بالنسبة لي؟
لشرح الأساسي للاستخدام المشترك للوالمتغيرات 'س' 'ص' في ويكيبيديا الصفحة الزائفة رمز (أو غيرها من تطبيقات أفضل من غربال أتكين)، قد تجد <لأ href = "HTTPS: الجواب //stackoverflow.com/questions/1569393/c-how-to-make-sieve-of-atkin-incremental/18342305#18342305">my على سؤال آخر ذي صلة مفيدة.
وفيما يلي ج ++ تنفيذ غربال أتكين التي قد تساعدك ...
#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;
}
