UIU: Prime Number using Square_Root Algorithm


প্রাইম নাম্বার: যে সংখ্যাকে 1 এবং ওই সংখ্যা ছাড়া আর কোন সংখ্যা দিয়ে ভাগ করা যায় না, সেগুলা প্রাইম নাম্বার।

যেকোন সংখ্যাকেই 1 দিয়ে ভাগ করা যায়
আর, যেকোন সংখ্যাকেই ওই সংখ্যা দিয়ে ভাগ করা যাবেই।

মনে করি, আমাদের একটা সংখ্যা দেয়া আছে n
এখন আমরা যেটা করব, 2 থেকে শুরু করে n – 1 পর্যন্ত সবগুলা সংখ্যা দিয়ে n-কে ভাগ করব

যদি কোন সংখ্যা দিয়েই ভাগ করা না যায় তাহলে n প্রাইম
আর যদি কোন সংখ্যা দিয়ে ভাগ করা যায় তাহলে n প্রাইম না

আমরা প্রথমে কতগুলা প্রাইম নাম্বার দেখি,
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 …. এইগুলা হল প্রাইম নাম্বার

// @BEGIN_OF_SOURCE_CODE

#include <cstdio>

int main(int argc, char *argv[]) {
	
	int n;	

	scanf ("%d", &n);

	for ( int i = 2; i < n; i++ ) {
		if (n % i == 0) {
			printf ("%d is not prime", n);
		}
	}
}

// @END_OF_SOURCE_CODE

#11: আমরা 2 থেকে n – 1 পর্যন্ত লুপ রান করবো

#12: if condition চেক করে দেখলাম, n-কে i দিয়ে ভাগ করা যায় কিনা
যদি ভাগ করা যায় তাহলে n প্রাইম হবে না

আমরা বুঝলাম কখন প্রাইম হবে না, কিন্তু তাহলে কখন প্রাইম হবে?

// @BEGIN_OF_SOURCE_CODE

#include <cstdio>

int main(int argc, char *argv[]) {
	
	int n;	

	scanf ("%d", &n);

	bool flag = true;

	for ( int i = 2; i < n; i++ ) {
		if (n % i == 0) {
			printf ("%d is not prime", n);
			flag = false;
		}
	}

	if (flag) {
		printf ("%d is prime", n);
	}
}

// @END_OF_SOURCE_CODE

#11: আমরা একটা bool variable নিলাম
আপনারা bool variable C++-এ পাবেন। জিনিসটা খুব সহজ
bool variable-এ মাত্র ২টা value রাখা যায়। হয় true নাহয় false
আমরা প্রথমে flag-এ true রাখলাম

#14-16: if condition-এর ভেতরে আসলে আমরা জানি, প্রাইম না
তখন আমরা flag-কে flase করে দিলাম

#20: flag চেক করে দেখছি, true কিনা

if (flag) {

}

এবং

if (flag == true) {

}

একই কথা

যদি flag == true হয়, তার মানে #16-তে কখনই আমরা যাই নাই

অতএব, n প্রাইম

এবার প্রাইমের পুরো ব্যপারটা আমরা একটা function-এর ভিতরে নিয়ে যাই

// @BEGIN_OF_SOURCE_CODE

#include <cstdio>

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

	return true;
}

int main(int argc, char *argv[]) {
	
	int n;	

	scanf ("%d", &n);

	if (isPrime(n)) {
		printf ("%d is prime\n", n);
	} else {
		printf ("%d is not prime\n", n);
	}
}

// @END_OF_SOURCE_CODE

#5: একটা function নিলাম, যাকে আমি একটা integer নাম্বার দিব
এবং সে আমাকে বলবে, ওই নাম্বারটা প্রাইম কিনা
যদি প্রাইম হয় তাহলে সে আমাকে true return করবে
আর যদি প্রাইম না হয় তাহলে সে আমাকে false return করবে

#9: if condition-এর ভিতরে আসা মানেই প্রাইম না, তাই না?
তাহলে আমরা সাথে সাথে return false করব
return করা মানে, এই function থেকে আমরা বের হয়ে যাব

#13: এই লাইনে আসা মানে কিন্তু #9 কাজ করে নাই। যদি #9 কাজ করত তাহলে আমরা isPrime() Function-এর ভিতরে থাকতাম না,
অনেক আগেই বের হয়ে যেতাম, কাজেই এইখানে আসলে আমরা বুঝবো #9 কাজ করে নাই এবং n প্রাইম

#22: isPrime(n) == true হলে, n প্রাইম .. সহজ ব্যপার, তাই না?

এবার আমরা আরেকটু সামনে আগাবো

1 থেকে 1000 পর্যন্ত কতগুলা প্রাইম আছে, সেটা বের করব
এবং এই কাজটা করতে আমাদের কতটুকু সময় লাগলো সেটাও বের করব

// @BEGIN_OF_SOURCE_CODE

#include <cstdio>
#include <ctime>

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

	return true;
}

int main(int argc, char *argv[]) {

	clock_t t = clock();

	int numberOfPrime = 0;

	for ( int i = 1; i <= 1000; i++ ) {
		if ( isPrime(i) ) {
			numberOfPrime++;
		}
	}

	t = clock() - t;

	printf ("Number of Prime: %d\n", numberOfPrime);

	printf ("Time needed: %f\n", ((float)t) / CLOCKS_PER_SEC);
}

// @END_OF_SOURCE_CODE

আপনি যদি Code::Blocks ব্যবহার করেন, তাহলে এমনিতেই প্রোগ্রাম রান করার পরে কতটুকু সময় লাগলো সেটা জানা যায়

আমি ধরে নিলাম আপনি Code::Blocks ব্যবহার করছেন না, তাহলে আপনি কি করবেন? আপনার জন্যই প্রোগ্রামটা এইভাবে করা
(ওহ! আপনার জন্য আমার দরদ দেখছেন? Code::Blocks না থাকলে আপনার কি হবে? কত টেনশন করি আপনার জন্য!
আসলে এইগুলা কিছুই না, আমার নিজের Code::Blocks নাই তো! এইজন্য আমাকে এইভাবে কোড করতে হইলো :()

#4: সময় নিয়ে কাজ করার জন্য এই Header File-টা লাগবে

#19: সময় গুনতে শুরু করলাম আমরা

#23-27: আমরা একটা লুপ রান করলাম 1 থেকে 1000 পর্যন্ত
তারপর if condition check করলাম
যদি isPrime(i) আমাদের true দেয় তাহলে i একটা প্রাইম .. তাই আমরা numberOfPrime++ করলাম

#29: সময় গণনা সমাপ্ত

output:
Number of Prime: 169
Time needed: 0.000000 second

একটু ভুল হয়ে গেল!

1000-এর নিচে প্রাইম আছে 168-টা
আমাদের তাহলে 169 আসলো কেন?

উপরের কোডে কোথাও কোন ভুল হল কিনা দেখেন, একটু চিন্তা করেন, তারপর নিচের লেখা পড়েন

আমাদের isPrime() Function ভুল করে একটা নাম্বারকে প্রাইম বলছে, কিন্তু সেটা আসলে প্রাইম না

ওই নাম্বারটা হল 1

n = 1 হলে #8 লুপটা রানই করবে না, তাই না?

সবচেয়ে ছোট প্রাইম হল 2
এবং 2 হল একমাত্র প্রাইম যেটা জোড় সংখ্যা

তাহলে আমরা isPrime() function-টা একটু ঠিকঠাক করি

bool isPrime(int n)
{
	if ( n < 2 ) return false;

	for ( int i = 2; i < n; i++ ) {
		if (n % i == 0) {
			return false;
		}
	}

	return true;
}

যদি n, 2 থেকে ছোট হয় তাহলে সাথে সাথে return false, নীচে যাওয়ার দরকারই নাই .. ঠিক আছে?

এইবার আবার রান করে দেখি

output:
Number of Prime: 168
Time needed: 0.000000 second

এখন ঠিক আছে 🙂

এবার 1000 বদলে 10000 করি, তারপর রান করি

output:
Number of Prime: 1229
Time needed: 0.021000 second

এবার 10000 বদলে 100000 করি, তারপর রান করি

output:
Number of Prime: 9592
Time needed: 1.669000 second

এবার 100000 বদলে 1000000 করি, তারপর রান করি

output:
Number of Prime: 78498
Time needed: 136.707001 second

Time needed-এর value আপনাদের ভিন্ন হতে পারে, এটা আমার কম্পিউটারের value

কথা সেইটা না .. কথা হইলো, আপনার কোড রান করতে কম্পিউটারের জান বের হয়ে গেছে!

খালি একটু চিন্তা করেন, আপনার কোড রান করতে কম্পিউটারের ১৩৬ সেকেন্ড লাগছে!

কনটেস্টে আপনার কোড যদি ৩ সেকেন্ডের মধ্যে রান করে শেষ না হয়, তাহলে আপনি Time Limit Exceed (TLE) খাবেন

আমরা বুঝতে পারলাম, আপনার এই প্রাইম কোডটার​ পারফরমেন্স খুবই খারাপ

একটা জিনিস খেয়াল করেছেন?
কিছুক্ষণ আগেও আমি সবখানে “আমাদের কোড”, “আমাদের কোড” বলতেছিলাম
যখনই দেখা গেল, কোডের​ পারফরমেন্স খারাপ, তখনই বলা শুরু করলাম, “আপনার কোড”, “আপনার কোড”

শুধু কোডিং শিখলে হবে? কিভাবে অন্যদের চকোলেট খাওয়াতে হয় সেটাও শিখেন! 😉

আমরা এখন কোডটার​ পারফরমেন্স ঠিক করব, কাজেই এটা আবার “আমাদের কোড”, ওকে? 😀

পারফরমেন্স ইমপ্রুভমেন্ট 1:

আমরা এতক্ষণ 2 থেকে শুরু করে n – 1 পর্যন্ত লুপ রান করাচ্ছিলাম
আমাদের আসলে 2 থেকে শুরু করে n / 2 এর বেশি যাবার দরকার নাই
কারন, n / 2 + 1 থেকে n – 1 পর্যন্ত কোন সংখ্যা দিয়ে n-কে ভাগ করা যাবে না

ব্যপারটা খুবই সাধারন। যেমন: ৫০ থেকে বড় কোন সংখ্যা দিয়েই ১০০-কে ভাগ করা যায় না

bool isPrime(int n)
{
	if ( n < 2 ) return false;

	for ( int i = 2; i <= n / 2; i++ ) {
		if (n % i == 0) {
			return false;
		}
	}

	return true;
}

এবার কোড রান করে দেখা যাক কতটুকু ইমপ্রুভমেন্ট হল

output:
Number of Prime: 78498
Time needed: 77.183998 second

কিছুটা ভাল হলেও, এখনও আপনার কোডের পারফরমেন্স তেমন ভাল না ..

পারফরমেন্স ইমপ্রুভমেন্ট 2:

আমরা জানি, 2 হল একমাত্র প্রাইম, যেটা জোড়
তার মানে 2 ছাড়া আর কোন জোড় সংখ্যাই প্রাইম হতে পারে না

কিভাবে এই ব্যপারটা কাজে লাগাতে হবে আমি ধাপগুলা বলি

1. n == 2 যদি হয়, তাহলে সাথে সাথে return true

2. তারপর দেখব, যদি n জোড় হয় তাহলে সাথে সাথে return false

3. এখন আমাদের কাছে শুধু বেজোড় সংখ্যা আছে
আমরা জানি, কোন বেজোড় সংখ্যাকেই, জোড় সংখ্যা দিয়ে ভাগ করা যায় না

4. তাহলে আমাদের লুপ শুরু হবে ৩ থেকে, ২ থেকে নয়

5. এবং আমাদের লুপ বাড়বে ২ করে, মানে হল,
৩, ৫, ৭, ৯, ১১ .. এইভাবে

মূলত আমরা যা করলাম: লুপ চালানোর আগেই সব জোড় সংখ্যাকে বাদ দিয়ে দিলাম

bool isPrime(int n)
{
	if ( n < 2 ) return false;

	if ( n == 2 ) return true;

	if ( n % 2 == 0 ) return false;

	for ( int i = 3; i <= n / 2; i += 2 ) {
		if (n % i == 0) {
			return false;
		}
	}

	return true;
}

এবার কোড রান করে দেখা যাক কতটুকু ইমপ্রুভমেন্ট হল

output:
Number of Prime: 78498
Time needed: 40.703999 second

40 second! এইটা কিছু হইল? কোথায় আমাদের লাগবে < 3 second , আর এইখানে আসছে 40 second

অনেক হইছে! আর সহ্য করা যায় না .. আপনার এই দেশী অ্যালগরিদম দিয়ে আর কাজ করা সম্ভব না

এখন আমাদের বিদেশী অ্যালগরিদম লাগবে
প্রথমে বিদেশী অ্যালগরিদমের কোডটা দেখি

পারফরমেন্স ইমপ্রুভমেন্ট 3:

// @BEGIN_OF_SOURCE_CODE

#include <cstdio>
#include <ctime>
#include <cmath>

bool isPrime(int n)
{
	if ( n < 2 ) return false;

	int squareRoot = (int) sqrt(n);

	for ( int i = 2; i <= squareRoot; i++ ) {
		if (n % i == 0) {
			return false;
		}
	}

	return true;
}

int main(int argc, char *argv[]) {

	clock_t t = clock();

	int numberOfPrime = 0;

	for ( int i = 1; i <= 1000000; i++ ) {
		if ( isPrime(i) ) {
			numberOfPrime++;
		}
	}

	t = clock() - t;

	printf ("Number of Prime: %d\n", numberOfPrime);

	printf ("Time needed: %f second\n", ((float)t) / CLOCKS_PER_SEC);
}

// @END_OF_SOURCE_CODE

রান করে দেখি কি অবস্থা

output:
Number of Prime: 78498
Time needed: 0.327000 second

ওহ! সুপারম্যান স্পীড .. এইটাইতো দরকার 😀

#11: আমরা n-এর square root বের করলাম
sqrt() আমাদের একটা double নাম্বার দেয় ..
আমাদের double দরকার হবে না, তাই আমরা (int) দিয়ে cast করে নিলাম
integer cast করা মানে হলো জোর করে integer বানানো, মানে আমরা শুধুমাত্র integer অংশটা আমরা পাব
একটা উদাহরণ দেই

// @BEGIN_OF_SOURCE_CODE

#include <cstdio>

int main(int argc, char *argv[])
{
    int n;

    n = (int) 7.6;

    printf ("%d\n", n);

    n = (int) 7.1;

    printf ("%d\n", n);

}

// @END_OF_SOURCE_CODE

output: 
7
7

আমাদের কেন double দরকার হবে না?

উত্তর: আমরা তো লুপ চালাচ্ছি .. আমাদের লুপ 1 করে increment হবে
তাই, square root result 7.6 হোক বা 7.1, আমরা আসলে 7 বারই ঘুরব

আচ্ছা, মনে করেন আমি ২টা কোড লিখলাম
কোড ২টা একই কাজ করে

// example 1
int squareRoot = (int) sqrt(n);

for ( int i = 2; i <= squareRoot; i++ ) {

}

// example 2
for ( int i = 2; i <= (int) sqrt(n); i++ ) {

}

কোন কোড রান করতে বেশি সময় লাগবে?

yes! example 2 কোড রান করতে বেশি সময় লাগবে
কারণ প্রতিবার লুপ condition চেক করার সময় সে একবার করে sqrt (n) ক্যালকুলেট করে
তাই আমরা example 1-এর মত করে কোড করব

প্রাইম নাম্বার ব্যপারটা একটু অন্যভাবে বলি,

আমাদের আসলে জানা দরকার, 1 এবং n ছাড়া n-এর আর কোন গুনিতক আছে কিনা

যদি থাকে, n প্রাইম না
যদি না থাকে, n প্রাইম
তাই না?

এবার আমরা যেটা করব, 2 থেকে sqrt (n) পর্যন্ত লুপ চালাবো

আমরা ধরে নিচ্ছি, যদি n-এর কোন গুনিতক থাকে (1 এবং n ছাড়া) তাহলে 2 থেকে sqrt(n)-এর মধ্যেই থাকবে
যদি না থাকে, তাহলে 2 থেকে sqrt(n)-এর বাইরেও থাকবে না

মজার ব্যপার হল, আমাদের এই ধারনা কাজ করতেছে, এবং খুব বেশি ভালভাবে কাজ করতেছে
কিন্তু কেন কাজ করছে সেটা হল বিষয়

ব্যপারটা আজব না? 2 থেকে sqrt(n)-এর মধ্যে গুনিতক পাওয়া না গেলে n-এর আর গুনিতক নাই, কাজেই প্রাইম

আমরা একটা উদাহরন দেখি,

মনে করি, একটা সংখ্যা ৩৬ দেয়া আছে
৩৬-এর গুনিতক গুলা কি কি?

1	x	36	= 36
2	x	18	= 36
3	x	12	= 36
4	x	9	= 36
6	x	6	= 36

একটা ব্যপার খেয়াল করেন, বামপাশের সংখ্যাগুলা আস্তে আস্তে বাড়ে।
যেমন: 1, 2, 3, 4, 6
এবং ডানপাশের সংখ্যাগুলা আস্তে আস্তে কমে।
যেমন: 36, 18, 12, 9, 6

একটু এলোমেলো হয়ে গেল না?

আমরা বলেছিলাম, 2 থেকে 6-এর মধ্যেই 36-এর গুনিতক পাওয়া যাবে। কিন্তু 6-এর চেয়ে বড় গুনিতকও আছে 36-এর। যেমন: 9, 12, 18

ব্যপারটা আসলে এরকম না

আমরা আসলে বলেছিলাম, যদি 36-এর গুনিতক থাকে তবে অবশ্যই 2 থেকে 6-এর মধ্যে থাকবে।
আমরা কিন্তু বলছি না, 6-এর চেয়ে বড় গুনিতক থাকবে না

মানে হল, 36-এর যদি ১০০টা গুনিতকও থাকে, তাহলে তার মধ্যে ১ টা 2 থেকে 6-এর মধ্যে থাকবেই।

আমাদের সবগুলা গুনিতকের দরকারও নাই। একটা পেলেই আমরা বলে দিতে পারব, 36 প্রাইম না

2 থেকে 6-এর মধ্যে যদি 36 এর গুনিতক পাওয়া না যায় তাহলে, বুঝতে হবে 36-এর কোন গুনিতকই নাই।

এবার আমরা প্রমান করব, আমাদের ধারনা কেন ঠিক
আমাদের প্রমান করার পদ্ধতির নাম Proof by Contradiction

ধরি, 2 থেকে 6-এর মধ্যে 36-এর কোন গুনিতক নাই, কিন্তু 6 থেকে বড় একটা গুনিতক আছে, যেটা হল P, তাহলে
P x Q = 36

36-এর একটা গুনিতক P
তারমানে, 36-কে P দিয়ে ভাগ করা যায় .. ভাগ করলে কিছু একটা রেজাল্ট আসবে, সেটাই হলো, Q
Q = 36 / P
or, P x Q = 36

আমরা একটু আগেই দেখেছিলাম,
6 x 6 = 36

যেহেতু P > 6 তাহলে অবশ্যই Q < 6

তাহলে 36-এর একটা গুনিতক পাওয়া গেল যেটা 6 থেকে ছোট

এটা Contradictory! কারন আমরা ধরে নিয়েছিলাম, 2 থেকে 6-এর মধ্যে 36-এর কোন গুনিতক নাই

কাজেই, 2 থেকে 6-এর মধ্যে যদি 36 এর গুনিতক পাওয়া না যায় তাহলে, 6 থেকে বড় 36-এর কোন গুনিতক থাকতে পারে না । (প্রমানিত)

Advertisements

6 thoughts on “UIU: Prime Number using Square_Root Algorithm

  1. চমৎকার !! খুব স্পষ্ট এবং ক্লিয়ার । 🙂 থ্যাঙ্ক ইয়উ ভাইয়া

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