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

একটি সংখ্যা $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.