এরাতোস্থেনেস ছাকনি
গণিতে, এরাতোস্থেনেস ছাকনি হলো একটি নির্দিষ্ট সীমার মধ্যে মৌলিক সংখ্যাসমুহ নির্ণয়ের প্রাচীন অ্যালগরিদম।
২ হতে শুরু করে এক এক করে যৌগিক সংখ্যা অর্থাৎ মৌলিক সংখ্যার গুণিতক সমুহ চিহ্নিত করে এটি কাজ করে। কোন মৌলিক সংখ্যার গুণিতক সমুহ সেই সংখ্যা হতে শুরু হয়ে একটি ধারা গঠন করে এবং ধরার প্রতিটি পদের পার্থক্য ধ্রুব থাকে এবং ঐ মৌলিক সংখ্যাটির সমান হয়। যখন মৌলিক সংখ্যার গুণিতক সমুহ চিহ্নিত করা শেষ হয়, বাকি থাকা সংখ্যাগুলোই মৌলিক।
সাধারণ বিবরণ
[সম্পাদনা]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 কিংবা অন্যান্য মৌলিক সংখ্যা ধরে ধাপ ৩ এর পুনরাবৃত্তি করতে হবে। যখন, তালিকার সর্বোচ্চ সংখ্যা হতে বড় হবে, তখন থামতে হবে।
বাদ পড়া সংখ্যা গুলোই মৌলিক সংখ্যা।
উদাহরণ
[সম্পাদনা]১ থেকে ৩০ পর্যন্ত মৌলিক সংখ্যা গুলো বের করতে হলে
প্রথমে ২ হতে ৩০ পর্যন্ত ৩০ পর্যন্ত সংখ্যাগুলোর তালিকা তৈরি করি:
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 3456789101112131415161718192021222324252627282930
এরপর তালিকাতে ৩ আছে। প্রতিবার ৩ যোগ করে ৩ এর গুণিতক সমুহ কেটে দিই।
2 3456789101112131415161718192021222324252627282930
এরপর ৫ এর গুণিতক সমুহ কেটে দিই।
2 3456789101112131415161718192021222324252627282930
এরপর ৭ এর গুণিতক সমুহ কাটতে হবে। কিন্তু ৭ এর গুণিতক সমুহ ইতোমধ্যে কাটা হয়েছে। যেহেতু (৭×৭) ৩০ এর চেয়ে বড়। তাই বাদ পড়া সংখ্যা গুলোই ৩০ এর নিচের মৌলিক সংখ্যা।
2 3 5 7 11 13 17 19 23 29
তথ্যসূত্র
[সম্পাদনা]- ↑ Clocksin, William F., Christopher S. Mellish, Programming in Prolog, 1984, p. 170. আইএসবিএন ৩-৫৪০-১১০৪৬-১.
বহিঃসংযোগ
[সম্পাদনা]- 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.