ඇල්ගොරිතම
(Algorithm වෙතින් යළි-යොමු කරන ලදි)
1. 2 සිට ප්රාථමිකතාව සඳහා ඔබට පරීකෂා කිරීමට අවශ්ය විශාලම සංඛ්යාව දක්වා සංඛ්යා ලයිස්තුවක් ලියන්න. එම ලයිස්තුව A ලෙස හදුන්වමු. (මෙය පින්තූරයේ වම් පස වු කොටු ලයිස්තුවයි)
2. වෙනත් සොයා ගත් ප්රාථමික සංඛ්යා සඳහා වු ලයිස්තුවක ප්රථම සංඛ්යාව වන 2 ලියන්න. මෙම ලයිස්තුව B ලෙස හදුන්වමු. (මෙය පින්තූරයේ දකුණු පස වු ලයිස්තුවයි) 3. 2 හි සියලු ගුණාකාර A ලයිස්තුවෙන් කපා හරින්න. 4. ලයිස්තුවේ ඉතිරි ප්රථම අංකය ප්රාථමික අංකයකි. එම අංකය B ලයිස්තුව ලියන්න. 5. එම අංකය හා එහි ගුණාකාර සියල්ල A ලයිස්තුවෙන් කපා හරින්න. ගුණාකාර කපාහැරීම අදාල සංඛ්යාවේ වර්ගයෙන් ආරම්භ කළ හැක. මන්දයත් ඊට පහලින් ඇති ගුණාකාර පෙර පියවරේදී දැනටමත් කපා හැර ඇත. 6. A ලයිස්තුවේ කිසිදු අංකයක් ඉතිරි නොවන තෙක් පියවර අංක 4 හා 5 නැවත නැවතත් සිදු කරන්න. ඔබ A ලයිස්තුවේ විශාලම සංඛ්යාවේ වර්ග මූලයට වඩා වැඩි සංඛ්යාවකට ලගා වු විට A ලයිස්තුවේ ඉතිරි සියලු සංඛ්යා ප්රාථමික සංඛ්යා වන බවද අවධානයට ගන්න.
පහත දැක්වෙන්නේ ඇල්ගොරිතම සදහා වු ව්යාජ කේතයක
// arbitrary search limit limit ← 1.000.000
// assume all numbers are prime at first
is_prime(i) ← true, i ∈ [2, limit]
for n in [2, √limit]:
if is_prime(n): // eliminate multiples of each prime, // starting with its square is_prime(i) ← false, i ∈ {n², n²+n, n²+2n, ..., limit}
for n in [2, limit]:
if is_prime(n): print n
References
සංස්කරණයhttp://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm