, , , ,

ইউলার প্রবলেম নাম্বার ১০

problem : The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.Find the sum of all the primes below two million.
https://projecteuler.net/problem=10


প্রবলেমটা বুজতে অসুবিধা হওয়ার কথা না।1 – 2000000 range এর মধ্যে সবগুলা প্রাইম নাম্বারের যোগফল বের করতে হবে।
এখানে মূল বিষয়টি হচ্ছে আপনাকে প্রোগ্রামটি efficient  করতে হবে।
প্রাইম নাম্বার বের করার অনেক গুলো কনসেপ্ট আছে
১. n number টি ১ এবং n দ্বারা বিভাজ্য হলে প্রাইম নতুবা প্রাইম না।
২. 1 থেকে  n/2 range এর মধ্যে যতগুলো  নাম্বার আছে সেগুলো দিয়ে যদি n বিভাজ্য হয় তাহলে n প্রাইম নাম্বার।
৩. 1 থেকে n পর্যন্ত  যতগুলো নাম্বার আছে তাদের মধ্যে শুধুমাত্র বিজোড় সংখ্যা গুলো চেক করতে হবে।(২ একমাত্র জোড় প্রাইম নাম্বার )।

১ নাম্বার লজিক দিয়ে সমস্যাটি সমাধান করা যাক


কি ব্যাপার execute হচ্ছে না কেন !!?? হবে ধৈর্য ধরে 8/9 মিনিট অপেক্ষা করুন হবে :D
উপরের বাকি লজিক গুলো দিয়ে সল্ভ করলেও একই অবস্থা হবে programming contest এ আপনার ৩/৪ সেকেন্ড  execution time  দেওয়া থাকে সেখানে এত সময় লাগলে হবে না।

এই ধরনের বড় বড় প্রাইম নাম্বার সমস্যা সমাধানের জন্য আপনাকে সিভ অফ এরাটস্থেনিজ(Sieve of Eratosthenes) অ্যালগরিদম জানতে হবে। সিভ মানে হল ছাঁকনি। এই এলগোরিদমে কম্পোজিট নাম্বারগুলো থেকে প্রাইম নাম্বারগুলোকে ছেঁকে আলাদা করা হয়। আর গ্রিক গণিতবিদ এরাটস্থেনিজ  (২৭৬ পূর্বাব্দ – ১৯৫ পূর্বাব্দ) এই এলগোরিদমের আবিষ্কারক বিধায় এলগোরিদমটির নাম দেওয়া হয়েছে ‘সিভ অফ এরাটস্থেনিজ’। দ্রুততার সাথে প্রাইম নাম্বার বের করার ক্ষেত্রে এলগোরিদমটি এতোটাই কার্যকর যে ২২০০ বছরের পুরোনো এই এলগোরিদম আজও কম্পিউটার বিজ্ঞানে ব্যবহার করা হয়! এর সাহায্যে ১০ মিলিয়নের মধ্যে অবস্থিত সকল প্রাইম নাম্বার অনায়াসেই বের করে ফেলা যায়।

সিভ অফ এরাটস্থেনিজ )Sieve of Eratosthenes)  থিওরিঃ সকল যৌগিক সংখ্যার অন্তত একটি উৎপাদক সংখ্যাটির বর্গমূলের ছোট বা সমান হবেই।অর্থাৎ n সংখ্যাটি prime হবে যদি √n এই সীমার মধ্যে একটি সংখ্যা দিয়েও n বিভাজ্য না হয়। 
সিভ অফ এরাটস্থেনিজ (Sieve of Eratosthenes)  থিওরি প্রয়োগ করে সমাধান






long long int  নেয়ার কারন হল int  by default  size 32 bit  long long  means 32+16+16=64 bit.
প্রথমে ধরা যাক নাম্বারটি প্রাইম তাই count=1, child লুপে চেক করা হয়েছে i প্রাইম কিনা এজন্য i কে একবার ভাগ করলেই হবে যদি i%j==0  হয় তাহলে সংখ্যাটি প্রাইম আর তা না হলে লুপ থেকে বের হয়ে যাবে এবং parent লুপে গিয়ে sum=sum+i হবে অর্থাৎ প্রাইম সংখ্যা গুলোকে যোগ করবে।


Projecteuler.net সাইটে আপনার সমাধান সঠিক হলে আপনি ঐ সমাধানের একটি উপর বিস্তারিত অ্যালগরিদম সহ একটি pdf file পাবেন যেখানে ঐ সমস্যা সমাধানের জন্য কি থিওরি ব্যাবহার করতে হবে সব বিস্তারিত ব্যাখ্যা করা আছে। তবে সমাধান না করা পর্যন্ত আপনি pdf file টি পাবেন না। নিচে ফাইলটির ডাউনলোড লিংক দেওয়া আছে ডাউনলোড করে নিতে পারেন,অনেক কিছুই জানতে পারবেন।

,

সিভ অফ এরাটস্থেনিজ (Sieve of Eratosthenes) প্রয়োগ করে প্রাইম নাম্বার বের করা

কোন একটা নাম্বার যদি প্রাইম না হয়, অর্থাৎ কম্পোজিট(যৌগিক সংখ্যা) হয় তাহলে সেই নাম্বারটার একটা ফ্যাক্টর (উৎপাদক) নাম্বারটির বর্গমূলের সমান বা তার থেকে ছোট হবেই” একটা উদাহরন দিলে মনে হয় এই কথাটার মানে বোঝা সহজ হবে।

ধরা যাক,আমাদের কাছে একটা কম্পোজিট নাম্বার আছে সেইটা হল ৯০। এখন একটা সিম্পল ক্যালকুলেটর দিয়ে আমরা √(৯০ ) এর মান বের করতে পারি। আমার পিসির ক্যালকুলেটর বলতেছে যে, √(৯০ ) এর মান হচ্ছে৯.৪৮৬৮৩২৯৮০৫০৫১৩৮। আমরা যেহেতু কোডিং এর সময় ইনটিজার ভ্যালু নিয়া কাজ করব তাই আমরা বলতে পারি যে √(৯০ ) এর মান সিমপ্লি ৯। আচ্ছা এই পর্যন্ত বোঝা গেল। এখন আমরা একটা জিনিস দেখি-


১*৯০=৯০
২*৪৫=৯০
৩*৩০=৯০
৫*১৮=৯০
৬*১৫=৯০
৯*১০=৯০

আমরা শুধু ৯০ কে দুইটি সংখ্যার গুনফল আকারে লিখেছি। এবং আসলে এইগুলাই হচ্ছে ৯০ এর সবগুলা ফ্যাক্টর। এখানে একটু লক্ষ করলেই দেখা যায় যে, বামপাশের কলামে যে ফ্যাক্টর গুলা আছে সেইগুলা √(৯০ ) এর সমান বা তার থেকে ছোট আর ডানপাশের কলামে যে ফ্যাক্টর গুলা আছে সেইগুলার মান √(৯০ ) এর সমান বা তার থেকে বড়। আবার আমাদের ক্যালকুলেটর থেকে করা হিসাব অনুযায়ী আমরা জানি যে √(৯০ ) এর মান ৯। তাহলে আমাদের থিওরি অনুযায়ী কি সব কিছ হচ্ছে?????? হা হচ্ছে। কারন আমাদের থিওরি তে বলা আছে যে, কম্পোজিট নাম্বারের একটা ফ্যাক্টর নাম্বারটির বর্গমূলের সমান বা তার থেকে ছোট হবে।  

এইখানে ৯০ এর ফ্যাক্টর গুলা হইতেসে ১,২,৩,৫,৬,৯,১০,১৫,১৮,৩০,৪৫ এবং ৯০। তাইলে এইখানে ৫টা ফ্যাক্টর আছে যাদের মান √(৯০ ) থেকে ছোট আর √(৯০ ) এর মান হচ্ছে ৯ তাই আমদেরথিওরিটা একদম পারফেক্ট ভাবে মিলে গেছে কারন ফ্যাক্টর গুলার মধ্যে ৯ ও আছে। এইখানে আর একটা মজার বিষয় লক্ষণীয় যে, ৯০= ৬*১৫(টেস্ট করার জন্য নিলাম আরকি) ৬ এবং ১৫ এর মধ্যে একটা হচ্ছে √(৯০ ) এর মান থেকে ছোট(এইক্ষেত্রে ৬) এবং আরেকটা √(৯০ ) এর থেকে বড় (এইক্ষেত্রে ১৫)। আবার ৯০=৯*১০ এর মধ্যে একটা হচ্ছে √(৯০ ) সমান(৯) আরেকটা হচ্ছে √(৯০ ) থেকে বড়।তো আমরা এইখান থেকে বলতে পারি যে, ৯০ এর
ফ্যাক্টর গুলার একটা যদি √(৯০ ) থেকে ছোট হয় তাহলে আরেকটা হবে √(৯০ )থেকে বড়। যদি তা না হয় তাহলে তাদের গুনফল ৯০ হবে না।গুনফল গুলা খেয়াল করলেই দেখা যায়।
তাহলে একটা নাম্বার n প্রাইম কিনা তা জানতে হলে √(n ) পর্যন্ত সংখ্যা দিয়ে ভাগ করলেই হয়ে যাবে। n বা n-1 বা n/2 পর্যন্ত সংখ্যা দিয়ে ভাগ করার কোনই দরকার নাই। কেন নিশ্চয়ই সবাই বুঝতে পারছে। কারন নাম্বারটা যদি প্রাইম হয় তাহলে √n এই সীমার মধ্যে একটা নাম্বার দিয়েও n ভাগ যাবে না।
এইবার আমরা code এ চলে আসিঃ 




এইবার আসা যাক কোডটাকে ব্যাখ্যা করার পালা।ধরা যাক, ১৭ প্রাইম
কিনা আমরা চেক করতে চাই।আমাদের এইখানে প্রথমেই আমরা একটা ভেরিয়েবল x এ আমাদের যে নাম্বারটাকে প্রাইমকিনা চেক করতে  চাই,তার বর্গমূল x এ এসাইন হবে। এক্ষেত্রে হবে ৪।
এরপরে for loop এর ভেতরে আমরা ৪ পর্যন্ত লুপ চালাই। লুপের ভিতেরে condition দেয়া আছে যে, যদি আমাদের 17,i দ্বারা ভাগ যায় তাহলে লুপটা ব্রেক হুয়ে যাবে। 2 দ্বারা ১৭ ভাগ যায় না। তাই i=3 হবে, ৩ দ্বারা ১৭ ভাগ যায় না তাই i=4 হবে। ৪ দ্বারা ১৭ ভাগ যায়না তাই i=5 হবে কিন্তু আমাদের x এর আছে ৪। তাই প্রোগ্রাম control লুপ থেকে বের হয়ে যাবে। এখন নিচে আরেকটা condition আছে   if(n>1 && i == x+1)। এখানে n>1এইটা সত্য(n=17 তাই) এবং i == x+1
এইটাও সত্য। কারন i এর ভেলু যখন ৫ হইসিল তখন লুপ থেকে আমরা বের হয়ে গেসিলাম। আবার x এর মান হইতেসে ৪ যার সাথে ১ যোগ করলে হয় ৫। তাই, ৫=৫ এইটা সত্য।তাই আমাদের নাম্বারটা প্রাইম।এইভাবে অন্যান্য নাম্বারগুলাও চেক করে দেখা যাবে প্রাইম কিনা।