https://projecteuler.net/problem=10
প্রবলেমটা বুজতে অসুবিধা হওয়ার কথা না।1 – 2000000 range এর মধ্যে সবগুলা প্রাইম নাম্বারের যোগফল বের করতে হবে।
এখানে মূল বিষয়টি হচ্ছে আপনাকে প্রোগ্রামটি efficient করতে হবে।
প্রাইম নাম্বার বের করার অনেক গুলো কনসেপ্ট আছে
১. n number টি ১ এবং n দ্বারা বিভাজ্য হলে প্রাইম নতুবা প্রাইম না।
২. 1 থেকে n/2 range এর মধ্যে যতগুলো নাম্বার আছে সেগুলো দিয়ে যদি n বিভাজ্য হয় তাহলে n প্রাইম নাম্বার।
৩. 1 থেকে n পর্যন্ত যতগুলো নাম্বার আছে তাদের মধ্যে শুধুমাত্র বিজোড় সংখ্যা গুলো চেক করতে হবে।(২ একমাত্র জোড় প্রাইম নাম্বার )।
১ নাম্বার লজিক দিয়ে সমস্যাটি সমাধান করা যাক
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<stdio.h> | |
| int main() | |
| { | |
| int i,j; | |
| int long long sum=0; | |
| int const long long num=2000000; | |
| for(i=1;i<=num;i++){ | |
| for(j=2;j<i;j++){ | |
| if(i%j==0) | |
| break; | |
| } // child loop | |
| if(i==j) | |
| sum=sum+i; | |
| } // parrent loop | |
| printf(" The sum of prime Number below %lld is %lld \n\n",num,sum); | |
| } //end main |
কি ব্যাপার execute হচ্ছে না কেন !!?? হবে ধৈর্য ধরে 8/9 মিনিট অপেক্ষা করুন হবে :D
উপরের বাকি লজিক গুলো দিয়ে সল্ভ করলেও একই অবস্থা হবে programming contest এ আপনার ৩/৪ সেকেন্ড execution time দেওয়া থাকে সেখানে এত সময় লাগলে হবে না।
এই ধরনের বড় বড় প্রাইম নাম্বার সমস্যা সমাধানের জন্য আপনাকে সিভ অফ এরাটস্থেনিজ(Sieve of Eratosthenes) অ্যালগরিদম জানতে হবে। সিভ মানে হল ছাঁকনি। এই এলগোরিদমে কম্পোজিট নাম্বারগুলো থেকে প্রাইম নাম্বারগুলোকে ছেঁকে আলাদা করা হয়। আর গ্রিক গণিতবিদ এরাটস্থেনিজ (২৭৬ পূর্বাব্দ – ১৯৫ পূর্বাব্দ) এই এলগোরিদমের আবিষ্কারক বিধায় এলগোরিদমটির নাম দেওয়া হয়েছে ‘সিভ অফ এরাটস্থেনিজ’। দ্রুততার সাথে প্রাইম নাম্বার বের করার ক্ষেত্রে এলগোরিদমটি এতোটাই কার্যকর যে ২২০০ বছরের পুরোনো এই এলগোরিদম আজও কম্পিউটার বিজ্ঞানে ব্যবহার করা হয়! এর সাহায্যে ১০ মিলিয়নের মধ্যে অবস্থিত সকল প্রাইম নাম্বার অনায়াসেই বের করে ফেলা যায়।
সিভ অফ এরাটস্থেনিজ )Sieve of Eratosthenes) থিওরিঃ সকল যৌগিক সংখ্যার অন্তত একটি উৎপাদক সংখ্যাটির বর্গমূলের ছোট বা সমান হবেই।অর্থাৎ n সংখ্যাটি prime হবে যদি √n এই সীমার মধ্যে একটি সংখ্যা দিয়েও n বিভাজ্য না হয়।
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <stdio.h> | |
| main() | |
| { | |
| long long int i,j,k,n=2000000,sum=2; | |
| int count; | |
| for(i=3;i<n;i++){ | |
| count=1; // assume that it is prime | |
| for(j=2;j<=sqrt(i);j++){ | |
| if(i%j==0){ | |
| count=0; // it is not prime | |
| break; | |
| } // end control flow | |
| } // end child loop | |
| if(count==1) | |
| sum=sum+i; | |
| } // end parent loop | |
| printf("%lld\n",sum); | |
| } // end main loop |
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 টি পাবেন না। নিচে ফাইলটির ডাউনলোড লিংক দেওয়া আছে ডাউনলোড করে নিতে পারেন,অনেক কিছুই জানতে পারবেন।
