মৌলিক সংখ্যা (Prime number)


Prime number বা মৌলিক সংখ্যা হচ্ছে সে সব সংখ্যা যার ১ এবং ঐ সংখ্যা ছাড়া আর কোন উৎপাদক নেই। অর্থাৎ ঐ সংখ্যাটি ১ এবং ঐ সংখ্যা ছাড়া নিঃশেষে বিভাজ্য নয়।

প্রোগ্রামারদের কাছে মৌলিক সংখ্যা খুব পছন্দের একটা বিষয়। যে কোন ধরনেন প্রোগ্রামিং প্রতিযোগিতায় সাধারনত অন্তত একটা সমস্যা থাকে প্রাইম নাম্বার থেকে। প্রাইম নাম্বার বের করার প্রোগ্রামটি খুব সহজেই লিখে ফেলা যায়।

কোডঃ

//Prime number check
//Author: Milon

#include<iostream>
using namespace std;

bool isPrime(int num){
    if(num<2)
        return false;
    for(int i=2;i<num;i++)
        if(num%i==0)
            return false;
    return tru e;
    }

int main(){
    int n;
    while(cin>>n && n){
        if(isPrime(n))
            cout<<n<<" is a prime number."<<endl;
        else
            cout<<n<<" is not a prime number."<<endl;
        }
    return 0;
    }

উপরের প্রোগ্রামটিতে সব গুলো সংখ্যা দিয়ে num কে ভাগ করা হয়েছে, যার আসলে কোন প্রয়োজন নেই। কারন কোন জোড় সংখ্যা কখনো প্রাইম নাম্বার হতে পারে না।
সেক্ষেত্রে প্রোগ্রামটি হবে-

কোডঃ

//Prime number check
//Author: Milon

bool isPrime(int num){
    if(num<2)
        return false;
    if(num==2)
        return true;
    if(num%2==0)
        return false;
    for(int i=3;i<num;i+=2)
        if(num%i==0)
            return false;
    return true;
    }

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

কোডঃ

//Prime number check
//Author: Milon

bool isPrime(int num){
    if(num<2)
        return false;
    if(num==2)
        return true;
    if(num%2==0)
        return false;
    for(int i=3;i<num/2;i+=2)
        if(num%i==0)
            return false;
    return true;
    }

অর্ধেক পর্যন্ত চেক করার প্রয়োজনও আসলে নাই। ঐ সংখ্যার বর্গমূল পর্যন্ত চেক করলেই চলে-

কোডঃ

//Prime number check
//Author: Milon

bool isPrime(int num){
    if(num==1)
        return false;
    if(num==2)
        return true;
    if(num%2==0)
        return false;
    for(int i=3;i*i<=num;i+=2)
        if(num%i==0)
            return false;
    return true;
    }

প্রাইম নাম্বার বের করার সবচেয়ে ভাল পদ্ধতি হচ্ছে Sieve of Eratosthenes. গ্রীক গণিতবিদ Eratosthenes এই পদ্ধতিটি আবিস্কার করেন। এই পদ্ধতিটিতে প্রথমে যে সংখ্যাগুলোর মধ্য থেকে প্রাইম নাম্বার বের করা হবে সেগুলিকে একটা অ্যারের মধ্যে রাখা হয়। মনে করি আমরা ১ থেকে ৫০ পর্যন্ত সংখ্যার মধ্যে প্রাইম নাম্বার বের করব। তাহলে prime নামের অ্যারের মধ্যে আমরা সংখ্যাগুলোকে রাখব। আমরা ধরে নিলাম এর সবগুলোই প্রাইম নাম্বার।
প্রথমে ০ এবং ১ প্রাইম নাম্বার না। তাই এ দুটোকে বাদ দিলাম। ২ প্রাইম সংখ্যা, কিন্তু এর গুনিতক একটাও প্রাইম নাম্বার না। তাই ৪, ৬, ৮, ১০, ১২ এগুলোকে বাদ দিলাম। এরপরের প্রাইম নাম্বার ৩। ৩ এর সব গুনিতক বাদ। এরপর ৪, কিন্তু ৪ আগেই বাদ পড়েছে। এরপর ৫ প্রাইম নাম্বার, ৫ এর সব গুনিতক বাদ। এভাবে চলতে চলতে ৫০ এর বর্গমূল পর্যন্ত চেক করলেই আমরা সব প্রাইম নাম্বার পেয়ে যাব।

কোডঃ

//Sieve of Eratosthenes
//Author: Milon

#include<cstdio>
#include<cmath>
using namespace std;

#define max 19000000

bool prime[max+1];

void sieve(){
    long int i,j;
    for(i=2;i<=max;i++)
        prime[i]=true;
    for(i=2;i*i<=max;){
        for(j=2*i;j<=max;j+=i){
            prime[j]=false;
            }
        i++;
        while(!prime[i])
            i++;
        }
    }

int main(){
    sieve();
    long int n;
    while(scanf("%ld",&n)==1){
        if(prime[n]==true)
            printf("prime\n");
        else
            printf("not prime\n");
        }
    return 0;
    }
Advertisements

4 thoughts on “মৌলিক সংখ্যা (Prime number)

  1. Very nice . Thanks for ur article. There is no doubt that ” Sieve of Eratosthenes” is better among all the technique.
    I think it can be optimized by modifyng “sieve()” function. It will give works for large prime number. For example, If I would like to find either 7 is prime or not, as “sieve()” function we have to calculate all the number till root of max. If we do same thing for given number-7 , it will give better output.

  2. আপনি ঠিকই বলেছেন, ভাই। sieve() এর আরো ভাল মেথড আছে। সেটা নিয়ে ভবিষ্যতে লেখার ইচ্ছা আছে।

  3. ভালো লাগলো। তবে প্রতিবারই সম্পূর্ণ code পড়তে কিছুটা বিরক্ত লেগেছে। একই code repeat না করলেই ভালো।

  4. ধন্যবাদ ভাই, আপনার মূল্যবান পরামর্শের জন্যে। এই ত্রুটি দূর করা হয়েছে।

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s