Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Correct the Sieve

Limits 1s, 512 MB

Sieve of Eratosthenes is a fast algorithm for finding prime numbers in larger ranges. According to Wikipedia, the algorithm works as follows:

To find all the prime numbers less than or equal to a given integer n by Eratosthenes’ method:

  • Create a list of consecutive integers from 2 through n: (2, 3, 4, …, n).
  • Initially, let p equal 2, the smallest prime number.
  • Enumerate the multiples of p by counting to n from 2p in increments of p, and mark them in the list (these will be 2p, 3p, 4p, … ; the p itself should not be marked).
  • Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.

When the algorithm terminates, the numbers remaining not marked in the list are all the primes below n.

Your friend Shrabonti is very excited after learning this algorithm and even coded it by following the pseudo code. She also managed to successfully solve a problem with her code. But when she has found another problem and submitted the same code, she found wrong answer. She got very surprised with this and shared her code with you. Here’s the code:

#include <stdio.h>

int isPrime[ 1000100 ] ; 
void sieve() {
	for( int i = 2 ; i <= 1000000 ; i ++ ) {
		isPrime[ i ] = 1 ; 
	}	
	for( int i = 2 ; i <= 1000000 ; i ++ ) {
		for( int j = i * i ; j <= 1000000 ; j += i ) {
			isPrime[ j ] = 0 ; 
		}
	}
}
int main() {
	sieve() ; 
	int N ; 
	scanf("%d",&N) ; 
	int num ; 
	for( int i = 0 ; i < N ; i ++ ) {
		scanf("%d",&num) ; 
		if( isPrime[ num ] == 1 ) {
			printf("%d is a prime number.\n",num);
		}
		else {
			printf("%d is not a prime number.\n",num);
		}
	}
	return 0 ; 
}

She has also provided you the problem statement for her problem. It says, “You will be given some integer numbers from 1 to 106. You have to tell whether each of those numbers are prime or not. The first line will contain an integer N, the amount of numbers that you will get. After that N lines follow, each line will have a number X from 1 to 106. If X is a prime, just prime “X is a prime number”, otherwise print “X is not a prime number”.

So help Shrabonti debug the given code. Or you can write a code of your own that produces the correct results.

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.


Discussion
Statistics

78% Solution Ratio

fsshakkhorEarliest, Dec '16

narutoFastest, 0.1s

muzahid.islamLightest, 28 MB

touhidurShortest, 219B

Submit

Login to submit