Prime Generator Problem

help
1

I am a newbiee here and this is my first post. I hope that I’m posting it in correct section.
So, I was trying to solve a problem Prime Generator in which we’ve to find all the prime numbers between 2 specified numbers.

Here’s my solution: CodeChef: Practical coding for everyone.
Is this a better method to find a prime number?

#include <stdio.h>

int main(void) {
int t, start, end, i;
scanf(“%d”, &t);
while(t–) {
start = 0;
end = 0;
scanf(“%d %d”, &start, &end);
for(i=start; i<=end; i++) {
if(i!=1) {
if(i==2 || i==3 || i==5 || i==7)
printf(“%d\n”, i);
else if(!(i%2==0) && !(i%3==0) && !(i%5==0) && !(i%7==0))
printf(“%d\n”, i);
}
}
printf(“\n”);
}
return 0;
}

2

This solution wouldn’t work for a number that is a product of two higher prime numbers.
Let’s say 247 (product of 13 and 19). It’s factors are (1, 13, 19, 247), so it is not a prime, but according to your program, it is not divisible by 2, 3, 5 or 7 so it must be prime, which is wrong.

According to me, the best method to find out if a number is prime is to iterate from 2 to its square root testing divisibility, and break as soon as you find the first factor.

3

Can be done using segmented sieve.

4

Here is a HINT : Every prime number except 2 and 3 is of the form 6N+1 or 6N-1.
Example : 7 = (6x1 +1) , 11 = (6x2 - 1) , 13=(6x2 + 1) , 17 = (6x3 - 1) and so on.

5

If only I had read this post when you posted it, I’d have passed all test cases in today’s NQT Digital coding problem.