## 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.

• Views:106,721 views
• Rating:
•  Click on the stars above to rate this page
• Categories:
• Tags:

J. Faust says:

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?

Chinni Krishna says:

for(j=2;j<=i-1;j++) it should be the statement you made wrong

Agamdeep Singh says:

to M.Wali M
in code blocks by default is shows execution time

MonEntertainment says:

#include
int main ()
{
int a,b,c,d,e;
printf (“toon”);
scanf(“%d”, a);

b=a%2;
c=a%3;
d=a%5;
e=a%7;
if (b>=1 && c>=1 && d>=1 && e>=1)
printf (“prime numbern”);
else
printf (“not prime numbern”);

return 0;

}

mayank goel says:

really great simple logic

Seth Erebos says:

Thank you so much, you explained it so much better then text could of.   I’m subscribing and seeing more of your videos thanx man 🙂

Kaushik Bhalerao says:

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

callme0800god says:

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

rushikesh patil says:

ty bro

Can you please make a video how to find all Mersenne number in c++

Rishi Kumar Soni says:

this is not TURBO C or DOSBOX can u tell me the name of the app

Amatul Uzma says:

thank u

Jia Qi Li says:

hi I like your explanation. But could you please specify the purpose of line 14 where says if ( I==j)?

Projjwal Maiti says:

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)) { for(j=2;(j*j)<=i;j+=((j%2)+1)) if(i%j == 0) break; if (j*j > i)
printf(“%dn”,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 {2,3,5,7,9,11,13,15,17,……,n} 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 = {2,3,5,7,9,11,13,15,17,......,sqrt(i)} (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(“%dn”,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 😉

shra v says:

any one can explain me. how the data floating in the loop.

Mohan Sarma says:

Crazy explanation sir

expert25 says:

You live up to your name of “Bad Tutorial”

Zerdy X says:

i need a program to start from having more than 100 000 000 digits so i’d make some quick money

Ramesh kumar says:

good sirrr

Max Shigeyoshi says:

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??

sammu el says:

this program is outputting only 1, and not any other prime numbers. can anyone help me?

Edson Pires says:

Thanks

Rebaona Mosiane says:

thank you so much it helped a lot!!!!

Alex Csillag says:

Can somebody please explain this to me?

Gudu Kasa says:

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

Prakash VL says:

Good Keep it up bud 🙂

Anika Lima says:

tnx

Mark Anderson says:

Thanks … nice tutorial for begineers 🙂
Using the same above mentioned process.. we can find all prime numbers between 1 to N
http://www.techcrashcourse.com/2015/11/c-program-to-print-all-prime-numbers-between-1-to-N.html

Rohan Nayak says:

what c compiler u are using? +Madhur Bhatia

JAI SHIDDHART says:

what is the version ur using

Kaushal Limbachiya says:

it has time complexity of O(n^2) .Is there any efficient way to solve this problem?