Prime Number Algorithms

প্রাইম নাম্বার এলগরিদম

প্রগ্রামিং প্রবলেম এ আমরা বিভিন্ন ধরনের প্রাইম নাম্বার ভিত্তিক প্রবলেম দেখি।
***** প্রাইম নাম্বার কোন গুলো?

প্রাইম নাম্বারঃপ্রাইম নাম্বার হচ্ছে যেই নাম্বার কে কেবল ঐ নাম্বার এবং এক দিয়ে ভাগ করা যায় তাছারা অন্য কোন নাম্বার দিয়ে ভাগ করা যায়না ঐ সকল নাম্বার কেই প্রাইম নাম্বার বলা হয় এবং ঐ নাম্বার ও এক এদের মধ্যে নুন্যতম দুরুত্ব থাকতে হবে। যেমন ,,,,১১,১৩ ইত্যাদি। এখানে প্রাইম নাম্বার নয় যদিও নিজ সংখ্যা ও কেবল দিয়েই বিভাজ্য অন্য কোন সংখ্যা দিয়ে নয়। এর কারন হচ্ছে নিজ সংখ্যা ও এর মধ্যে নুন্যতম দুরুত্ব নেই।যেমন ১-১=০ ।সুতরাং প্রাইম নাম্বার এর আওতায় নেই। কিন্তু ২-১=১ এখানে নিজ সংখ্যা ও এক দিয়ে কেবল বিভাজ্য অন্য কোন নাম্বার দিয়ে বিভাজ্য নয় এবং নিজ(২) সংখ্যা এর মধ্যে নুন্যতম দুরুত্ব আছে।সুতরাং প্রাইম নাম্বার।

এখন আমরা কিছু লজিক বের করব যার মাধ্যমে আমরা খুব সহজে প্রাইম নাম্বার বের করতে পারব। এবং এমন লজিক বের করার চেষ্ট্রা করব যাতে রান টাইম আমরা কমাই নিয়ে আসতে পারি। প্রথমে এমন কয়েকটি সংখ্যা নেই যেই সংখ্যাগুলো প্রাইম নয়। যেমন ৬০,১০০,৫০০,১০০০,১২১,১১৫

এই সংখ্যাগুলোর উতপাদক যদি বের করি তাহলে আমরা একটা বিষয় লক্ষ করতে পারব দেখা যাক বিষয়টা কি?

যেমন :

৬০ এর উতপাদক হচ্ছে ২,২,৩,৫।

১০০ এর উতপাদক হচ্ছে ২,২,৫,৫।

৫০০ এর উতপাদক হচ্ছে ২,২,৫,৫,৫।

১০০০ এর উতপাদক হচ্ছে ২,২,২,৫,৫,৫।

১২১ এর উতপাদক হচ্ছে ১১,১১।

উপরের বিষয় টি আমরা লক্ষ করলে দেখতে পাব যে যে সকল নাম্বারগুলো আসলে মৌলিক নয় সেকল নাম্বারগুলো অবশ্যই মৌলিক নাম্বারের সমন্ময়ে গঠিত এবং সেই সকল মৌলিক নাম্বার গুলোর মধ্যে অন্তত একটি নাম্বার এমন হবে যে অবশ্যই ঐ(অমৌলিক) নাম্বারটির বর্গ করলে যেই নাম্বার টি পাওয়া যাবে সেই বর্গ নাম্বার থেকে ছোট অথবা সমান আমরা এই লোজিক টি কাজে লাগিয়ে মৌলিক সংখ্যা বের করতে পারি এবং রান টাইম ও কমাই আনতে পারি।

নিচে সম্পুর্ন এই লোজিক টির উপর ভিত্তি করে একটা প্রগ্রাম দেওয়া হল আশা করি কাজে দিবে।


#include

#include

 

using namespace std;

//int Total;

int anotherprime(int a)

{

int CHECK = 1;

if(a==2||a==3||a==5||a==7)

return 1;

for(int i=2;i<=sqrt(a);i++)

{

//Total++;

if(a%i==0)

{

CHECK = 4;

return 2;

}

}

if(CHECK==1)

return 1;

}

int prime(int arr[],int check,int m)

{

int Copycheck,sqr=sqrt(check),CHECK=1;

if(check==1)

return 2;

if(check==2||check==3||check==5||check==7)

return 1;

for(int k=0;k=sqrt(check)+1)

break;

if(check%arr[k]==0)

{

CHECK = 4;

return 2;

}

}

if(CHECK==1)

return 1;

 

}

int main()

{

int num,arr[1000],m=0,alamin,count=0;

cout << "Please Enter a number"<< endl;

cin>>num;

for(int j=2;j<=sqrt(num);j++)

{

//Total++;

alamin = anotherprime(j);

if(alamin==1)

{

arr[m] = j;

m++;

}

}

for(int i=2;i<=num;i++)

{

//Total++;

int cary = prime(arr,i,m);

if(cary==1)

{

count++;

cout << i << " ";

}

 

}

cout << endl;

//cout << count << " " << Total << endl;

return 0;

 

}