[Solved] Code and Algorithm Explained — Get all prime numbers using the fastest and best technique –Tricks to remember this algorithm forever

Prime numbers are all numbers which are either divisible by itself of by 1 for example 2, 3, 5, 7

Now, to check if the number is prime number we need to check if that number is not multiple of anything other than 1 or the number itself.

Algorithm

1. Loop i from number 2 to given number say n
   for(int i = 2; i < n; i++) //Loop from 2 to 100
2. Now have another loop j from i to n
   for(int j = i; (i * j)>0 && (i * j) < n; j++) //Get all Non Prime Numbers
3. Get all i*j and store it in array such that it marks if the number is not prime
   AllNotPrime[i * j] = true; (where AllNotPrime is bool[n])
4. All left out numbers are prime.
   if (!AllNotPrime[i])

How to think of solving this algorithm? (Or how to remember this algorithm forever)

1. To show all prime numbers, we get all non-prime numbers and all left out are prime numbers so get all multiples, say 2*3, 2*4, Mark these numbers as non-prime numbers
2. We already do 2*3 so to avoid 3*2 we use j=i in inner loop
3. 1 is not a prime number so start your loop from 2
4. For any given number, Imagine a grid containing 10 numbers in each row and what you are coding for is marking all non-prime numbers, for example:

5. Once you have marked all multiples, loop all numbers and display all primes.

Click here for Complete Code