C Programming Tutorial - 42: Finding Prime Numbers

In this tutorial we are going to use nested loops to find prime numbers between 2 and 100.

[gudukasa]

Madhura, your tutorial is one of the best tutorials. Short and easy to understand. I appreciated!!

[projjwalmaiti]

Here is a logic where we can achive a better performance over constant resources (time over space).
We can just modify the algorithim by eleminating the most obvious non primes.

for(i=2;i<=n;i+=((i%2)+1))
{

if(i%j == 0)
break;
if (j*j > i)
printf("%d\n", i);
}

Complexities :-

Space= K
Time = 0.25 * n^1.5 = O(n^1.5)

Explanation :-

FYI...
A. The outer loop is listing each numbers.
B. The inner loop is checking whether the number is prime or not.

1. Why do we start from "i = 2" ?

Let us start with the definition of primes . A number having exactly 2 factors is prime.
All numbers except 1 has at least 2 factors 1 and itself. Thus making 1 definitely not a prime (but a co-prime).
So we can definitely ignore the check for 1. Thus we start from 2.

2. Why is the incremental logic "i+=((i%2)+1)" ?

Again all the even numbers except 2 are not primes cause it is divisible by two thus having a factor other than itself and 1.
So we can exclude all the even numbers after 2. if i is odd, (i%2)+1 is 2 thus getting the next odd number, if i is even (i%2)+1 is 1 also getting the next odd number.
This will generate a sequence for i ;- which is which will reduce the search space by 2.

3. Why do we start from "j = 2" ?

A number having exactly 2 factors is prime also means, that if a number has a factor in between 1 and itself then its not prime.
So here we are searching for a factor other than 1 and itself which will make the number a non prime if we find one.
So we start with 2 and not 1.

4. Why do we end at "(j*j) <= i" ?

This is the most trickiest part.
We have employed a principle of multiplication here if p*k = g then either p <= root(g) or q <= root(g).
So for any number g the number of factors less than its square root is exactly equal to the number of factors greater than its square root.
So if there exists a factor except 1 and itself for i then there must be at least one of them between 2 to sqrt(i)
This means j <= sqrt(i) or (j * j) <= i.

5. Why is the incremental logic "j+=((j%2)+1)" ?

Here again we have generated the series j = (how? see 2.)
We are generating the odd numbers along with 2 till sqrt(i) for the divisibility test. We can ignore the even numbers as if i is divisible by any even number that means i will also be divisible by 2. and we need to find just one factor other than 1 and itself to prove its not prime.

6. What is the purpose of "if(i%j == 0) break; "?

If j is a factor of i then i will be divisible by j or i%j will leave the reminder 0. If so we know its not prime we do not need to check for this any more we can move on to the next i. so we use break to pre-maturely exit from the inner loop where j*j will always be less than i.
On the contrary, if no factors are found the loop is exited maturely where j*j will always be greater than i.

7. What is the purpose of "if (j*j > i) printf("%d\n", i); "?

We need to print the prime numbers. So for only those cases of i which has exited the inner loop maturely (Ref. see 6) i is prime. So we print i if the inner loop is exited maturely i.e. (j*j > i).

I hope I made it easy for you guys to understand.

Thanks!

With Love,
-PK ;)

[thebtechboys]

Superb bro you had explained it in a very easy way these type of teaching is required for children to get intresting in the coding subject

[tchgszdok]

*finally*, thank u so much, you have no idea how much time I was bumping my head against the desk to figure out how to do this

[nmana]

Took me a while to understand it. I understood better when i wrote my thought process on a paper. Thank you!

[asoliev]

Very simple and easy to understand. I appreciate

[JFaust-sgqi]

Thank you for the tutorial. I've written a paper on prime numbers and I have a hypothesis that there may be a better way for a computer to find prime numbers. The problem is that I have literally no idea how to program and wouldn't even know where to begin in taking my paper and turning it into a computer program. If any computer programmers out there want to give me hand here, we may be able to build a computer program much more efficient at finding prime numbers. Anyone interested?

[ayae]

Thank you. Thanks to you I finally understood nested loops.

[aleksanderslepowronski]

instead of j <= i you can actually use
j <= i / 2 so there will be 2 times less calculations. None of the natural number can be divided by number bigger than half of it to get another natural number

[mfarsalanHD]

Thank you for explaining the prime numbers! Very helpful!

[DevaWay]

Why does "break" break out of the inner "for" and not only out of the "if"?

[nohpasbicol]

This is the problem our teacher will be giving for our major exam tom! Now I have to take a picture of this program to copy tom. LOL

[antoniokrzelj]

Dude u r legend ngl keep up the good work!!

[secular]

great really looks simple done in a simple way

[Shrutisingh-bbyp]

Can't understand reason behind
if (i==j)
Make me understand. Plz

[TallAleTales]

Hey.I'm having trouble with this bit of code. When I run, nothing appears on the screen. I've check several times, and i'm sure that my code is the same as what is one screen. any ideas??

[bhaleraok]

which compiler do you use ?
btw why did you changed your channel name ?

[loki]

How does % work here? Is that specific to c syntax?

[callmegod]

Very good!
How about use the while loop instead "nested loop"? 

[chandushingirikonda]

Why we are not taking initial value as 1 in i and j