এরাতোস্থেনেস ছাকনি

গণিতে, এরাতোস্থেনেস ছাকনি হলো একটি নির্দিষ্ট সীমার মধ্যে মৌলিক সংখ্যাসমুহ নির্ণয়ের প্রাচীন অ্যালগরিদম।

এরাতোস্থেনেস ছাকনি: ১২১ পর্যন্ত মৌলিক সংখ্যা নির্ণয়ে অ্যালগরিদমের ধাপ।

২ হতে শুরু করে এক এক করে যৌগিক সংখ্যা অর্থাৎ মৌলিক সংখ্যার গুণিতক সমুহ চিহ্নিত করে এটি কাজ করে। কোন মৌলিক সংখ্যার গুণিতক সমুহ সেই সংখ্যা হতে শুরু হয়ে একটি ধারা গঠন করে এবং ধরার প্রতিটি পদের পার্থক্য ধ্রুব থাকে এবং ঐ মৌলিক সংখ্যাটির সমান হয়। যখন মৌলিক সংখ্যার গুণিতক সমুহ চিহ্নিত করা শেষ হয়, বাকি থাকা সংখ্যাগুলোই মৌলিক।

সাধারণ বিবরণ

Sift the Two's and Sift the Three's:
The Sieve of Eratosthenes.
When the multiples sublime,
The numbers that remain are Prime.

Anonymous

মৌলিক সংখ্যা হলো সেই সকল স্বাভাবিক সংখ্যা যাদের কেবল মাত্র দুইটি গুণনিয়ক রয়েছে। মৌলিক সংখ্যাকে কেবল মাত্র ১ এবং সেই সংখ্যাটি দ্বারা ভাগ করা যায়।

n এর সমান কিংবা ছোট সংখ্যাগুলোর মাঝে মৌলিক সংখ্যাগুলো ইরাতোস্থিনিস অ্যালগরিদম এর সাহায্যে বের করতে:

• 2 থেকে n পর্যন্ত সংখ্যাগুলোর তালিকা করতে হবে।
• প্রাথমিকভাবে, ধরি p=2, যা প্রথম মৌলিক সংখ্যা।
• p থেকে p এর গুণিতকসমুহ n পর্যন্ত চিহ্নিত করি। ( p কে চিহ্নিত করা যাবে না।)
• পর্যায়ক্রমে, p= 3, 5 কিংবা অন্যান্য মৌলিক সংখ্যা ধরে ধাপ ৩ এর পুনরাবৃত্তি করতে হবে। যখন, $p^{2}$ তালিকার সর্বোচ্চ সংখ্যা হতে বড় হবে, তখন থামতে হবে।

বাদ পড়া সংখ্যা গুলোই মৌলিক সংখ্যা।

উদাহরণ

১ থেকে ৩০ পর্যন্ত মৌলিক সংখ্যা গুলো বের করতে হলে

প্রথমে ২ হতে ৩০ পর্যন্ত ৩০ পর্যন্ত সংখ্যাগুলোর তালিকা তৈরি করি:

 2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 

তালিকার প্রথম সংখ্যা 2। প্রতিবার 2 যোগ করে পরবর্তী সংখ্যাগুলো কেটে দেই। :

 2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 

এরপর তালিকাতে ৩ আছে। প্রতিবার ৩ যোগ করে ৩ এর গুণিতক সমুহ কেটে দিই।

 2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 

এরপর ৫ এর গুণিতক সমুহ কেটে দিই।

 2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 

এরপর ৭ এর গুণিতক সমুহ কাটতে হবে। কিন্তু ৭ এর গুণিতক সমুহ ইতোমধ্যে কাটা হয়েছে। যেহেতু (৭×৭) ৩০ এর চেয়ে বড়। তাই বাদ পড়া সংখ্যা গুলোই ৩০ এর নিচের মৌলিক সংখ্যা।

 2  3     5     7           11    13          17    19          23                29

বহিঃসংযোগ

• primesieve – Very fast highly optimized C/C++ segmented Sieve of Eratosthenes
• Eratosthenes, sieve of at Encyclopaedia of Mathematics
• Interactive JavaScript Page
• Sieve of Eratosthenes by George Beck, Wolfram Demonstrations Project.
• Sieve of Eratosthenes in Haskell
• Sieve of Eratosthenes algorithm illustrated and explained. Java and C++ implementations.
• A related sieve written in x86 assembly language
• Fast optimized highly parallel CUDA segmented Sieve of Eratosthenes in C
• SieveOfEratosthenesInManyProgrammingLanguages c2 wiki page
• The Art of Prime Sieving Sieve of Eratosthenes in C from 1998 with nice features and algorithmic tricks explained.