Error in code for generating prime numbers upto 10^5

Code : [click][1]

Since there are 9592 prime numbers between 1 to n , I have declared an array a having 9592 elements. We know that 2 and 3 are primes so I have stored them in the array directly. Starting from 4 till 100000 , each number i is checked for divisibility starting from j = i / 2 till we find a number which divides i . When such a number is found, we know that i is not a prime and so a[n] (starting from n = 2) is assigned a value of -1 and n is incremented by 1. If i % j != 0, variable u is incremented by 1. For each i , if (u == (i / 2) - 1) , i is stored in the array a because it’s a prime. (not divisible by any number in the range i / 2 to 2)
[1]: http://ideone.com/9ktYpM

@gautam94 : For the “Runtime error” you are getting , you are putting a[n] = -1 whenever a number is identified “not prime” according to your logic and a[n] = i whenever a number is identified “prime” according to your logic . So basically you are storing an entry for every number whether prime or not . Hence you need an array of size 10^5 .

Advice : You should not store anything when the number is not prime .

1 Like

@gautam94 : To check for “primality” , you need to check only till the square root of the number , not half of the number .

Consider 120

It can be factorized as :

1 * 120

2 * 60

3 * 40

4 * 30

5 * 24

6 * 20

8 * 15

10 * 12

Factors always appear in pairs . One is less than the square root and other is greater than the square root . ( The only exception being when the number is a perfect square then the square root is “pair factor” of square root ) .

So , if you checked till square root and didn’t find any prime number , you can be sure you won’t find ahead since if there exists a prime later then a corresponding prime less than or equal to square root would already have been found .

1 Like

@gautam94 Can you please describe your approach?

This part:

u = 0;
for (j = 2; j <= sqrt(i); ++j)
{
	if (i % j == 0)
	{	
		break;
	}	
	else
	{
		u = u + 1;
	}	
}
if (u == sqrt(i) - 1)
{
	a[n] = i;
	n = n + 1;
}

what is the meaning of that code? If j devides i then break…

http://ideone.com/sdqUgY It’s too slow. I am getting the correct output after about 7-8 seconds.

http://ideone.com/sdb13x I am unable to figure out the error.

I wrote a blog about sieve, maybe it will help you :wink:

http://codeforces.com/blog/entry/3519

2 Likes

The break statement is used to break the inner for loop because divisibility by just one number ius enough for us to know that i is not a prime and so we dont need to check for divisibility by other numbers (j). If i is not divisible by j, u is incremented by one each time. Now, for each i, if u is equal to sqrt (i) - 1 (which means i is not divisible by any number from 2 to sqrt(i)), the number is a prime and hence it is added to position n in the array a.

…so you want to check, that 5 is prime or not, steps…

i = 5, u = 0
j = 2
2 does not divide 5 => u = 1
3 is bigger than sqrt(5)
u is NOT sqrt(i) - 1 => a[n] is not set...

Is your statement

u is equal to sqrt (i) - 1 (which means i is not divisible by any number from 2 to sqrt(i))

correct?

edit: btw, you know that in if (u == sqrt(i) - 1) you compares int with double, right?

1 Like

I’ll try implementing Sieve of Eratosthenes. Thanks for the link.

in fact, it is very similar to what you have actually, the name is not so important, you just need to do correct operations…

@betlista I think that statement is correct. sqrt(5) = 2.23, but since I am using int it will be 2 and so according to m code u should be equal to 1 .

for compiler it’s not int to int comparison, but double to double, it has something to do with explicit and implicit casting, you can easily test it with

printf( "res=%c\n", 2 == sqrt(5) ? 'Y' : 'N' );

@betlista http://ideone.com/CEMoHZ I used the typecast operator for converting sqrt(i) to int and it worked. :smiley: It’s much faster than my first solution. Now I’ll try the Sieve.

1 Like

@gautam94 A very simple auxiliary standard approach. Use a variable, say flag, which is initialized as false (or any initail value you like) just before the for loop. When you encounter the condition (i%j == 0) as true, add flag = true; (or any other value than the initial value you used for initialization) and then break out of the loop. Now, after the for loop, all you need to test is whether the value of flag is the same as the initial value. If it is, then number is prime. Otherwise, not.

1 Like