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

**Price:**~~$17.00~~ $13.01

#### Python Crash Course, 2nd Edition: A Hands-On, Project-Based Introduction to Programming

(as of September 21, 2020 - More infoProduct prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on [relevant Amazon Site(s), as applicable] at the time of purchase will apply to the purchase of this product.)**Price: $189.98**

#### The Art of Computer Programming, Volumes 1-4A Boxed Set

Volume 1: Fundamental Algorithms Volume 2: Seminumerical Algorithms Volume 3: Sorting and Searching Volume 4A: Combinatorial Algorithms (as of September 21, 2020 - More infoProduct prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on [relevant Amazon Site(s), as applicable] at the time of purchase will apply to the purchase of this product.)**Price: $0.99**

#### 3.1 If-Then-Else

(as of September 21, 2020 - More infoProduct prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on [relevant Amazon Site(s), as applicable] at the time of purchase will apply to the purchase of this product.)**Price:**~~$41.19~~ $33.40

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?

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

to M.Wali M

in code blocks by default is shows execution time

how about this guys is it wrong???

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

}

really great simple logic

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 🙂

which compiler do you use ?

btw why did you changed your channel name ?

Very good!

How about use the while loop instead “nested loop”?

ty bro

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

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

thank u

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

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 😉

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

Crazy explanation sir

You live up to your name of “Bad Tutorial”

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

good sirrr

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

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

Thanks

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

Can somebody please explain this to me?

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

Good Keep it up bud 🙂

tnx

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

what c compiler u are using? +Madhur Bhatia

what is the version ur using

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

Pls send this editor on my email

ı am really greatfull