লিনিয়ার সিভ#

একটি সংখ্যা $n$ দেওয়া আছে, $[2;n]$ সেগমেন্টে সব মৌলিক সংখ্যা খুঁজে বের করুন।

এই কাজটি সমাধানের প্রচলিত উপায় হলো এরাটোস্থেনিসের সিভ ব্যবহার করা। এই অ্যালগরিদমটি অত্যন্ত সরল, কিন্তু এর রানটাইম $O(n \log \log n)$।

যদিও সাবলিনিয়ার রানটাইমের (অর্থাৎ $o(n)$) অনেক পরিচিত অ্যালগরিদম আছে, নিচে বর্ণিত অ্যালগরিদমটি এর সরলতার জন্য আকর্ষণীয়: এটি ক্লাসিক এরাটোস্থেনিসের সিভের চেয়ে বেশি জটিল নয়।

তাছাড়া, এখানে দেওয়া অ্যালগরিদমটি একটি পার্শ্বফল হিসেবে $[2; n]$ সেগমেন্টের সব সংখ্যার উৎপাদক বিভাজন হিসাব করে, এবং এটি অনেক ব্যবহারিক প্রয়োগে সহায়ক হতে পারে।

এই অ্যালগরিদমের দুর্বলতা হলো এটি ক্লাসিক এরাটোস্থেনিসের সিভের চেয়ে বেশি মেমরি ব্যবহার করে: এর জন্য $n$ সংখ্যার একটি অ্যারে প্রয়োজন, যেখানে ক্লাসিক সিভের জন্য $n$ বিট মেমরিই যথেষ্ট (যা ৩২ গুণ কম)।

সুতরাং, বর্ণিত অ্যালগরিদমটি শুধুমাত্র $10^7$ মাত্রার সংখ্যা পর্যন্ত ব্যবহার করা বুদ্ধিমানের কাজ এবং এর বেশি নয়।

অ্যালগরিদমটি Paul Pritchard এর কাজ। এটি (Pritchard, ১৯৮৭: নিবন্ধের শেষে রেফারেন্স দেখুন) এ Algorithm 3.3 এর একটি ভ্যারিয়ান্ট।

অ্যালগরিদম#

আমাদের লক্ষ্য হলো $[2; n]$ সেগমেন্টের প্রতিটি সংখ্যা $i$ এর জন্য সবচেয়ে ছোট মৌলিক গুণনীয়ক $lp [i]$ হিসাব করা।

এছাড়াও, আমাদের সব পাওয়া মৌলিক সংখ্যার তালিকা সংরক্ষণ করতে হবে - একে $pr []$ বলি।

আমরা $lp [i]$ এর মানগুলো শূন্য দিয়ে ইনিশিয়ালাইজ করবো, যার মানে হলো আমরা ধরে নিচ্ছি সব সংখ্যা মৌলিক। অ্যালগরিদম চলাকালীন এই অ্যারে ধীরে ধীরে পূরণ হবে।

এখন আমরা ২ থেকে $n$ পর্যন্ত সংখ্যার মধ্য দিয়ে যাবো। বর্তমান সংখ্যা $i$ এর জন্য আমাদের দুটি ক্ষেত্র আছে:

• $lp[i] = 0$ - এর মানে হলো $i$ মৌলিক, অর্থাৎ আমরা এর কোনো ছোট গুণনীয়ক পাইনি। তাই আমরা $lp [i] = i$ নির্ধারণ করি এবং $pr[]$ তালিকার শেষে $i$ যোগ করি।

• $lp[i] \neq 0$ - এর মানে হলো $i$ যৌগিক, এবং এর সবচেয়ে ছোট মৌলিক গুণনীয়ক হলো $lp [i]$।

উভয় ক্ষেত্রেই আমরা $i$ দ্বারা বিভাজ্য সংখ্যাগুলোর জন্য $lp []$ এর মান আপডেট করি। তবে, আমাদের লক্ষ্য হলো প্রতিটি সংখ্যার জন্য $lp []$ এর মান সর্বোচ্চ একবার সেট করা শেখা। আমরা এটি নিচের মতো করে করতে পারি:

ধরি $x_j = i \cdot p_j$ সংখ্যাগুলো বিবেচনা করি, যেখানে $p_j$ হলো $lp [i]$ এর সমান বা ছোট সব মৌলিক সংখ্যা (এই কারণেই আমাদের সব মৌলিক সংখ্যার তালিকা সংরক্ষণ করতে হয়)।

আমরা এই আকারের সব সংখ্যার জন্য একটি নতুন মান $lp [x_j] = p_j$ সেট করবো।

এই অ্যালগরিদমের সঠিকতার প্রমাণ এবং এর রানটাইম ইমপ্লিমেন্টেশনের পরে পাওয়া যাবে।

ইমপ্লিমেন্টেশন#

const int N = 10000000;
vector<int> lp(N+1);
vector<int> pr;

for (int i=2; i <= N; ++i) {
	if (lp[i] == 0) {
		lp[i] = i;
		pr.push_back(i);
	}
	for (int j = 0; i * pr[j] <= N; ++j) {
		lp[i * pr[j]] = pr[j];
		if (pr[j] == lp[i]) {
			break;
		}
	}
}

সঠিকতার প্রমাণ#

আমাদের প্রমাণ করতে হবে যে অ্যালগরিদম সব $lp []$ মান সঠিকভাবে সেট করে, এবং প্রতিটি মান ঠিক একবার সেট হয়। ফলে অ্যালগরিদমের রানটাইম হবে লিনিয়ার, কারণ অ্যালগরিদমের বাকি সব কাজ স্পষ্টতই $O (n)$ এ সম্পন্ন হয়।

লক্ষ্য করুন প্রতিটি সংখ্যা $i$ এর ঠিক একটি রূপ আছে:

যেখানে $lp [i]$ হলো $i$ এর সবচেয়ে ছোট মৌলিক গুণনীয়ক, এবং সংখ্যা $x$ এর $lp [i]$ এর চেয়ে ছোট কোনো মৌলিক গুণনীয়ক নেই, অর্থাৎ

এখন, আমাদের অ্যালগরিদমের কাজের সাথে তুলনা করা যাক: প্রকৃতপক্ষে, প্রতিটি $x$ এর জন্য এটি সব মৌলিক সংখ্যার মধ্য দিয়ে যায় যেগুলো দিয়ে এটি গুণ করা যায়, অর্থাৎ $lp [x]$ পর্যন্ত সব মৌলিক সংখ্যা সহ, উপরে দেওয়া আকারের সংখ্যা পেতে।

ফলে, অ্যালগরিদম প্রতিটি যৌগিক সংখ্যার মধ্য দিয়ে ঠিক একবার যাবে, সেখানে সঠিক $lp []$ মান সেট করবে। প্রমাণ সম্পন্ন।

রানটাইম ও মেমরি#

যদিও $O(n)$ রানটাইম ক্লাসিক এরাটোস্থেনিসের সিভের $O(n \log \log n)$ এর চেয়ে ভালো, তাদের মধ্যে পার্থক্য এত বড় নয়। বাস্তবে লিনিয়ার সিভ এরাটোস্থেনিসের সিভের একটি সাধারণ ইমপ্লিমেন্টেশনের মতোই দ্রুত চলে।

এরাটোস্থেনিসের সিভের অপটিমাইজড ভার্সনগুলোর তুলনায়, যেমন সেগমেন্টেড সিভ, এটি অনেক ধীর।

এই অ্যালগরিদমের মেমরি প্রয়োজনীয়তা বিবেচনা করলে - দৈর্ঘ্য $n$ এর একটি $lp []$ অ্যারে, এবং দৈর্ঘ্য $\frac n {\ln n}$ এর একটি $pr []$ অ্যারে, এই অ্যালগরিদম প্রতিটি দিক থেকে ক্লাসিক সিভের চেয়ে খারাপ মনে হয়।

তবে, এর মুক্তিদায়ক গুণ হলো এই অ্যালগরিদম একটি $lp []$ অ্যারে হিসাব করে, যা $[2; n]$ সেগমেন্টের যেকোনো সংখ্যার উৎপাদক বিভাজন সেই বিভাজনের আকারের সময়ে খুঁজে বের করতে দেয়। তাছাড়া, শুধুমাত্র একটি অতিরিক্ত অ্যারে ব্যবহার করলে উৎপাদক বিভাজন খোঁজার সময় ভাগ এড়ানো সম্ভব।

সব সংখ্যার উৎপাদক বিভাজন জানা অনেক কাজের জন্য অত্যন্ত উপকারী, এবং এই অ্যালগরিদম সেই কয়েকটির মধ্যে একটি যা লিনিয়ার সময়ে সেগুলো খুঁজে বের করতে দেয়।

রেফারেন্স#

• Paul Pritchard, Linear Prime-Number Sieves: a Family Tree, Science of Computer Programming, vol. 9 (1987), pp.17-35.