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

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

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

শুধুমাত্র লুপিং আর কন্ডিশন জানা থাকলেই মৌলিক সংখ্যার প্রোগ্রাম সহজেই লিখে ফেলা যায়। যেহেতু প্রোগ্রামিং কনটেস্টে C, C++, JAVA এবং PASCEL ভাষা ছাড়া অন্য কোন ভাষায় প্রোগ্রামিং করা যায় না, সেহেতু আমি সি++ ভাষাই বেছে নিচ্ছি। এর কারন বাংলাদেশে অধিকাংশ মানুষই প্যাসকেল ভাষায় প্রোগ্রামিং চর্চা করে না(আমি নিজেও এ ভাষা জানি না)। জাভা ভাল কিন্তু এর এক্সিকিউশন টাইম অনেক বেশি। বাকি রইল সি আর সি++। সি++ এর এস.টি.এল(স্ট্যান্ডার্ড টেমপ্লেট লাইব্রেরী) এর জন্য প্রোগ্রামারদের প্রথম পছন্দ। তাই আমি আমার প্রোগ্রামিং কোডগুলো সি++ প্রোগ্রামিং ভাষাতেই দিচ্ছি।

//Prime number check

#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

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

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

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

#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;
    }

এই লেখাটি ইতিপূর্বে আমার ব্যক্তিগত ব্লগ আগন্তুকের ব্লগ এ প্রকাশিত হয়েছে।

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

milon521 লিখেছেন:

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

ভালো হয়েছে।আরো পোস্ট আশা করছি  smile

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

ধন্যবাদ।
আমিও চেষ্টা করব ভবিষ্যতে এ ধরনের পোষ্ট আরও দিতে।

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

ইস! প্রগ্রামিংএর কিছুই বুঝিনা আমি।

এখনো অনেক অজানা ভাষার অচেনা শব্দের মত এই পৃথিবীর অনেক কিছুই অজানা-অচেনা রয়ে গেছে!! পৃথিবীতে কত অপূর্ব রহস্য লুকিয়ে আছে- যারা দেখতে চায় তাদের নিমন্ত্রণ।

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

এই এলগোরিদমটা অসাধারণ হলেও, এটার সবচেয়ে ভাল ব্যবহার হয় n-সংখ্যক মৌলিক সংখ্যা বের করতে অথবা n-তম মৌলিক সংখ্যা বের করার জন্য। কোন একটা সংখ্যা মৌলিক কিনা সেটা বের করার জন্য এই পদ্ধতি খুব দক্ষতার পরিচয় দেয় না। যেমন - একে যদি বলা হয় ১৭ মৌলিক সংখ্যা কিনা। তাহলে সে ঐ max-সংখ্যক সংখ্যার মৌলিকত্ব বের করবে তারপর উত্তর দেবে। তাহলে এখানে অহেতুক গণনা করা হচ্ছে। এক্ষেত্রে সহজ পদ্ধতিগুলোই ভাল।

তবে ইরাটোসথিনেসের এই এলগোরিদমকে আরও একটু উন্নত করা যায়। মানে মেমরি ইফিশিয়েন্ট করা যায়। প্রোগ্রামটি এখানে দিলাম। এটা সি++-এ করা। যা কোন একটা সংখ্যা পর্যন্ত যতগুলো মৌলিক সংখ্যা আছে তা বের করবে।

এটাকেই আরেকটু পরিবর্তন করে n-তম মৌলিক সংখ্যাও বের করার আরেকটি প্রোগ্রাম এখানে। এটা পাইথনে লেখা। এটা লিখেছিলাম এখানেই শিপলুর দেয়া একটা কনটেস্ট-এর জন্য। কিন্তু সেই প্রতিযোগিতার কোন ফলাফল পাওয়া যায়নি। sad

অফটপিকঃ (হাঙরিকোডার সমীপে)
এখানে gist পোস্ট করার জন্য একটা বিবিকোড থাকলে ভাল হত।

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

কোন একটা সংখ্যা মৌলিক কিনা তা চেক করার জন্য সিভ এর উপরের এ্যালগরিদমটাই সবচেয়ে ইফিশিয়েন্ট।
সিভ আর হাজার ভাবে কোড করা যায়। আমি সবচেয়ে সহজটা এখানে দিয়েছি। এটি ইফিশিয়েন্ট করার আরও অনেক বুদ্ধি আছে।
সিভ ডায়নামিক প্রোগ্রামিং মেথড ব্যবহার করে। আসলে সিভ ব্যবহার করা হয় যখন টেস্ট কেসের সংখ্যা ৫লাখ বা ১০ লাখ। তখন কোন সংখ্যা মৌলিক কিনা তা বার বার বের করার চেয়ে ঐ সংখ্যাটির জন্য সিভের ইন্ডেক্স চেক করাটাই উচিৎ।
স্বপ্নচারী ভাই, মন্তব্য করার জন্য আপনাকে ধন্যবাদ।

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

অসাধারণ।মিলন ভাই। smile আপনার লজিক আমার খুব ভাল লাছে। specially আপনার লজিক ছোট করার প্রক্রিয়াটা। আপনি আমাদের জন্য এমন আর কিছু বেসিক টিউটোরিয়াল দিবেন সে আশাই করি। smile

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

পুরোনো টপিক কে বাম্প করার জন্য দুঃখিত । আমি পাইথনে একদম নতুন। উদাসীন ভাইয়ের পাইথনে করা প্রোগ্রাম টার অনেক কিছুই বুঝি নাই । কিন্তু এম আই টি ওপেন কোর্স ওয়্যারে ১০০০ তম মৌলিক সংখ্যা বের করার জন্য কিছু হিন্টস দিছে । যা বুঝতে পারী নাই । sad
1.
Initialize some state variables
2.
Generate all (odd) integers > 1 as candidates to be prime
3.For each candidate integer, test whether it is prime
a.One easy way to do this is to test whether any other integer > 1 evenly divides the candidate with 0 remainder. To do this, you can use modular arithmetic, for example, the expression a%b returns the remainder after dividing the integer a by the integer b.
b.You might think about which integers you need to check as divisors – certainly you don’t need to go beyond the candidate you are checking, buthow much sooner can you stop checking?
4.
If the candidate is prime, print out some information so you know where you are in the computation, and update the state variables
5.
Stop when you reach some appropriate end condition. In formulating this condition, don’t forget that your program did not generate the first prime (2).
এই নির্দেশনা গুলোকে কেউ যদি প্রোগ্রামিং কে হেল্প করার মত করে বাংলা করে দেন ভাল হত ।  smile

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

@ত্রিনিত্রির রাশিমালা, পয়েন্টগুলো ভাল করে পড়লেই তো বুঝা যায়।

মিলন ভাইকে ধন্যবাদ এই টপিকটার জন্যে। এতদিন ধরে দেখিনি roll

১০

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

@ তারেক ভাই বুঝলে কি আর ফোরামে দিতাম । ইংরেজী আর গনিতে একেবাইরেই কাচা আমি  sad

১১

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

যদিও মিলন ভাইয়ের পোস্টেই সব বলে দেওয়া আছে, তবুও একটা হেল্প করছি। যদিও এটা পুরোটাই অনুবাদ নয়

১। কিছু ভেরিয়েবল ইনিশিয়ালাইজ করতে বলছে। যেমন ধরা যাক, i, j, primeCount ইত্যাদি যেগুলা লাগে
২। ১ এর চেয়ে বড় সব বিজোড় ইন্টিজার জেনারেট করতে হবে যেগুলা টেস্ট করা হবে প্রাইম কিনা।
৩। জেনারেট করা ইন্টিজার গুলাকে চেক করতে হবে প্রাইম কিনা
    ক) একটা হতে পারে মডুলাস বের করা। a%b সমান যদি ০ হয় তাহলে বলা যায় এটা প্রাইম নয়।
    খ) লুপে ফেলেও চেক করা যায়। প্রশ্ন হচ্ছে কতক্ষণ ধরে চেক করা হবে? চেক করা হয় ১৯ প্রাইম কিনা, তাহলে কি ১৯ পর্যন্ত লুপ চালিয়ে যেতে হবে? ( মিলন ভাইয়ের পোস্টে বলা আছে কতক্ষণ লুপ চালাতে হবে )
৪। যদি প্রাইম হয়, তাহলে প্রয়োজনীয় কাজ সারতে হবে। যেমন primeCount এর মান ১ বাড়ানো অথবা অন্য কিছু
৫। যখন আমাদের কন্ডিশন পূরণ হবে, তখন থামতে হবে। যেমন primeCount এর মান ১০০০ হওয়া।

১২

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

৪ বছর আগে এই কোড করতে আঙ্গুল ভাঙার উপক্রম হয়েছিল ।  tongue

১৩

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

তারেক ভাই কিছুটা বাচালেন । a এবং b মানে যেকোন বিজোড় ইন্টেজার ? তাই নয় কি ?ক্লাস থেকে এসে পাইথনে প্রোগ্রাম টা লিখব হেল্প কইরেন ।

১৪ সর্বশেষ সম্পাদনা করেছেন সাইফুল_বিডি (১১-০৯-২০১১ ১৪:২৯)

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

এই কোড টা দেখেন মনে হয় অনেক সোজা
C তে করা
#include<stdio.h>
#include<conio.h>
void main(){
clrscr();
int a,b,c;
printf("Put a number=");
scanf("%d",&b);
if(b<3){
printf("\n%d is a prime number",b);}
else{
for(a=2;a<=b-1;a++){
c=b%a;
if(c==0){
         printf("\n%d Is not a prime number  ",b);
         goto exit; }

}     printf("\n%d is a prime number",b);
}
exit:
getch();}

এই ব্যাক্তির সকল লেখা কাল্পনিক , জীবিত অথবা মৃত কারো সাথে মিল পাওয়া গেলে তা সম্পুর্ন কাকতালীয়, যদি লেখা জীবিত অথবা মৃত কারো সাথে মিলে যায় তার দায় এই আইডির মালিক কোনক্রমেই বহন করবেন না। এই ব্যক্তির সকল লেখা পাগলের প্রলাপের ন্যায় এই লেখা কোন প্রকার মতপ্রকাশ অথবা রেফারেন্স হিসাবে ব্যবহার করা যাবে না।

১৫

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

saaiful লিখেছেন:

এই কোড টা দেখেন মনে হয় অনেক সোজা
C তে করা
#include<stdio.h>
#include<conio.h>
void main(){
clrscr();
int a,b,c;
printf("Put a number=");
scanf("%d",&b);
if(b<3){
printf("\n%d is a prime number",b);}
else{
for(a=2;a<=b-1;a++){
c=b%a;
if(c==0){
         printf("\n%d Is not a prime number  ",b);
         goto exit; }

}     printf("\n%d is a prime number",b);
}
exit:
getch();}

কোডটা ঠিকমতই কাজ করে।তবে ২টি ব্যাপারঃ
১.conio.h হেডার ফাইলটি স্ট্যান্ডার্ড নয়
২.b-1 পর্যন্ত যাওয়ার দরকার হয়না।b এর রুট পর্যন্ত যাওয়াই যথেষ্ট

১৬

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

if(c==0) এইটা বুঝলাম না,যদি b=4 input দেই তাহলে
১ম লুপ c=0,
২য় লুপ c=1 হবে, এরপর if(c==0) statement টা কিভাবে কাজ করবে এইটা বুঝলামনা।

Like Security.

১৭ সর্বশেষ সম্পাদনা করেছেন সাইফুল_বিডি (০৫-০৩-২০১৩ ০৮:৪৮)

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

আপেল মাহমুদ লিখেছেন:

if(c==0) এইটা বুঝলাম না,যদি b=4 input দেই তাহলে
১ম লুপ c=0,
২য় লুপ c=1 হবে, এরপর if(c==0) statement টা কিভাবে কাজ করবে এইটা বুঝলামনা।

যদি কোন পদ্ধতিতে c=0 হয়ে যায় তখনি ওই নাম্বারটা প্রাইম না তা প্রমান হয়ে যায়। নিচে দেখুনঃ

if(c==0){
printf("\n%d Is not a prime number  ",b);
goto exit; }

exit:
getch();}

এখানে exit নামে একটা লেভেল আছে , যখন c=0 হবে তখন এটা exit লেভেলে জাম্প করবে। যদিও goto কে অনেকেই স্ট্যান্ডার্ড মানেন না , এটা আমার লেখা প্রথম প্রাইম ডিটেক্টর সো অনেক আজিব জিনিশ পাইবেন big_smile

এই ব্যাক্তির সকল লেখা কাল্পনিক , জীবিত অথবা মৃত কারো সাথে মিল পাওয়া গেলে তা সম্পুর্ন কাকতালীয়, যদি লেখা জীবিত অথবা মৃত কারো সাথে মিলে যায় তার দায় এই আইডির মালিক কোনক্রমেই বহন করবেন না। এই ব্যক্তির সকল লেখা পাগলের প্রলাপের ন্যায় এই লেখা কোন প্রকার মতপ্রকাশ অথবা রেফারেন্স হিসাবে ব্যবহার করা যাবে না।

১৮

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

C  তে সাধারণত if(c==0) এভাবে লেখার চেয়ে এভাবে লেখা স্মার্টতর if(!c)

"সংকোচেরও বিহ্বলতা নিজেরই অপমান। সংকটেরও কল্পনাতে হয়ও না ম্রিয়মাণ।
মুক্ত কর ভয়। আপন মাঝে শক্তি ধর, নিজেরে কর জয়॥"

১৯

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

আরণ্যক লিখেছেন:

C  তে সাধারণত if(c==0) এভাবে লেখার চেয়ে এভাবে লেখা স্মার্টতর if(!c)

আসলে না। সি তে অনেক শর্টহ্যান্ড থাকলেও ডিবাগ করার সুবিধার জন্য সেগুলো ব্যবহার রিকমেন্ড করা হয়না। যেমন x=x+1, x++, x+=1 একই রেজাল্ট দেয়। কিন্তু কোডের ভুল ত্রুটি বের করার সুবিধার জন্য প্রথমটা রিকমেন্ডেড।

২০

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

forhan লিখেছেন:
আরণ্যক লিখেছেন:

C  তে সাধারণত if(c==0) এভাবে লেখার চেয়ে এভাবে লেখা স্মার্টতর if(!c)

আসলে না। সি তে অনেক শর্টহ্যান্ড থাকলেও ডিবাগ করার সুবিধার জন্য সেগুলো ব্যবহার রিকমেন্ড করা হয়না। যেমন x=x+1, x++, x+=1 একই রেজাল্ট দেয়। কিন্তু কোডের ভুল ত্রুটি বের করার সুবিধার জন্য প্রথমটা রিকমেন্ডেড।

হার্বাড শীলের মতে প্রথম ভাবে এ্যামেচাররা আর পরেরটা প্রফেশনাল সি প্রোগ্রামাররা ব্যবহার করেন।

"সংকোচেরও বিহ্বলতা নিজেরই অপমান। সংকটেরও কল্পনাতে হয়ও না ম্রিয়মাণ।
মুক্ত কর ভয়। আপন মাঝে শক্তি ধর, নিজেরে কর জয়॥"