Correct the Sieve

Replay of SUB Intra Unive...
Limits 1s, 512 MB

সিভ অফ ইরাতোসথেনিস হলো বড় রেঞ্জের উপর দ্রুত প্রাইম সংখ্যা খুঁজে বের করার দ্রুতগতির অ্যালগরিদম। এই অ্যালগোরিদম দিয়ে n পর্যন্ত প্রাইম খুঁজে পাবার প্রক্রিয়াটি নিম্নরূপ:

  • প্রথমে ২ থেকে n পর্যন্ত পূর্ণসংখ্যার একটা তালিকা তৈরি করি।
  • শুরুতে p সমান ২ নিলাম।
  • p এর সব গুণিতক যারা p থেকে বড় কিন্তু এন এর ছোট বা সমান এদের নিলাম এবং লিস্টে তাদেরকে চিহ্ন দিয়ে রাখলাম।
  • পি থেকে বড় লিস্টের প্রথম সংখ্যা যেটিকে এখনো চিহ্ন দেওয়া হয় নি, সেটা p তে নিলাম, এবার ৩ নম্বর ধাপের পূনরাবৃত্তি করলাম। যদি আর কোন সংখ্যা বাকি না থাকে, তাহলে থামলাম।

উপরের প্রণালীটি শেষ হবার পর লিস্টের যে সংখ্যাগুলোকে এখনো চিহ্নিত করা হয় নি, সেগুলোই প্রাইম।

তোমার বন্ধু শ্রাবন্তী এই অ্যালগরিদমটি শিখে খুব আনন্দিত হলো এবং কোড করে ফেললো। সেই কোড দিয়ে একটা প্রবলেম মিলেও গেলো শ্রাবন্তীর। কিন্ত আরেকটি প্রবলেমে যখন একই কোডটি লিখলো সে, তখন ভুল উত্তর আসলো। কোডে কোন ভুল খুঁজে না পেয়ে শ্রাবন্তী কোডটা তোমাকে দিলো। কোডটা নিচে দেওয়া হলো:

 1#include <stdio.h>
 2
 3int isPrime[ 1000100 ] ; 
 4void sieve() {
 5	for( int i = 2 ; i <= 1000000 ; i ++ ) {
 6		isPrime[ i ] = 1 ; 
 7	}	
 8	for( int i = 2 ; i <= 1000000 ; i ++ ) {
 9		for( int j = i * i ; j <= 1000000 ; j += i ) {
10			isPrime[ j ] = 0 ; 
11		}
12	}
13}
14int main() {
15	sieve() ; 
16	int N ; 
17	scanf("%d",&N) ; 
18	int num ; 
19	for( int i = 0 ; i < N ; i ++ ) {
20		scanf("%d",&num) ; 
21		if( isPrime[ num ] == 1 ) {
22			printf("%d is a prime number.\n",num);
23		}
24		else {
25			printf("%d is not a prime number.\n",num);
26		}
27	}
28	return 0 ; 
29}

শ্রাবন্তীকে যে প্রবলেমটা দেওয়া হয়েছিল সেটা ছিল এমন:

"তোমাকে ১ থেকে ১০০০০০০ পর্যন্ত সংখ্যা দেয়া হবে, তোমাকে বলতে হবে সংখ্যাগুলো প্রাইম কি না। প্রথম লাইনে একটি সংখ্যা N দেওয়া থাকবে। সংখ্যাটি নির্দেশ করবে যে, এরপর তোমাকে আরো N সংখ্যক সংখ্যা দেওয়া হবে। এরপর তোমাকে N টি আলাদা আলাদা এক্স দেওয়া হবে, যেখানে প্রতিটি এক্স এর মান ১ থেকে ১০০০০০০ পর্যন্ত হবে। প্রতিটি এক্সের জন্য তোমাকে বলতে হবে সংখ্যাটি প্রাইম কি না। প্রাইম হলে প্রিন্ট করতে হবে, "X is a prime number", না হলে প্রিন্ট করতে হবে "X is not a prime number"।

এখন তাহলে শ্রাবন্তীর কোডটা ডিবাগ করে ফেলো। চাইলে তুমি নিজেও একটা নির্ভুল কোড লিখতে পারো।

Sample

InputOutput
10
2
3
5
4
6
7
10
9
71
21
2 is a prime number.
3 is a prime number.
5 is a prime number.
4 is not a prime number.
6 is not a prime number.
7 is a prime number.
10 is not a prime number.
9 is not a prime number.
71 is a prime number.
21 is not a prime number.

Submit

Login to submit.

Statistics

81% Solution Ratio
subintra2016.12$7Z9DgEarliest, Nov '16
Yasir_ArafatFastest, 0.1s
Shahe_NoorLightest, 5.7 MB
ShuddhoShortest, 194B
Toph uses cookies. By continuing you agree to our Cookie Policy.