Printing prime numbers from 1 through 100

Solution 1:

Three ways:

1.

int main () 
{
    for (int i=2; i<100; i++) 
        for (int j=2; j*j<=i; j++)
        {
            if (i % j == 0) 
                break;
            else if (j+1 > sqrt(i)) {
                cout << i << " ";

            }

        }   

    return 0;
}

2.

int main () 
{
    for (int i=2; i<100; i++) 
    {
        bool prime=true;
        for (int j=2; j*j<=i; j++)
        {
            if (i % j == 0) 
            {
                prime=false;
                break;    
            }
        }   
        if(prime) cout << i << " ";
    }
    return 0;
}

3.

#include <vector>
int main()
{
    std::vector<int> primes;
    primes.push_back(2);
    for(int i=3; i < 100; i++)
    {
        bool prime=true;
        for(int j=0;j<primes.size() && primes[j]*primes[j] <= i;j++)
        {
            if(i % primes[j] == 0)
            {
                prime=false;
                break;
            }
        }
        if(prime) 
        {
            primes.push_back(i);
            cout << i << " ";
        }
    }

    return 0;
}

Edit: In the third example, we keep track of all of our previously calculated primes. If a number is divisible by a non-prime number, there is also some prime <= that divisor which it is also divisble by. This reduces computation by a factor of primes_in_range/total_range.

Solution 2:

If j is equal to sqrt(i) it might also be a valid factor, not only if it's smaller.

To iterate up to and including sqrt(i) in your inner loop, you could write:

for (int j=2; j*j<=i; j++)

(Compared to using sqrt(i) this has the advantage to not need conversion to floating point numbers.)

Solution 3:

If a number has divisors, at least one of them must be less than or equal to the square root of the number. When you check divisors, you only need to check up to the square root, not all the way up to the number being tested.

Solution 4:

This is my very simple c++ program to list down the prime numbers in between 2 and 100.

for(int j=2;j<=100;++j)
{
    int i=2;
    for(;i<=j-1;i++)
    {
        if(j%i == 0)
            break;
    }

    if(i==j && i != 2)
        cout<<j<<endl;
}

Solution 5:

Using Sieve of Eratosthenes logic, I am able to achieve the same results with much faster speed.

My code demo VS accepted answer.

Comparing the count, my code takes significantly lesser iteration to finish the job. Checkout the results for different N values in the end.

Why this code performs better than already accepted ones:

- the even numbers are not checked even once throughout the process.

- both inner and outer loops are checking only within possible limits. No extraneous checks.

Code:

int N = 1000; //Print primes number from 1 to N
vector<bool> primes(N, true);
for(int i = 3; i*i < N; i += 2){    //Jump of 2
    for(int j = 3; j*i < N; j+=2){  //Again, jump of 2
        primes[j*i] = false;
    }
}
if(N >= 2) cout << "2 ";
for(int i = 3; i < N; i+=2){        //Again, jump of 2
    if(primes[i] == true) cout << i << " "; 
}

For N = 1000, my code takes 1166 iterations, accepted answer takes 5287 (4.5 times slower)

For N = 10000, my code takes 14637 iterations, accepted answer takes 117526 (8 times slower)

For N = 100000, my code takes 175491 iterations, accepted answer takes 2745693 (15.6 times slower)