Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Printing prime numbers from 1 through 100

This c++ code prints out the following prime numbers: 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97.

But I don't think that's the way my book wants it to be written. It mentions something about square root of a number. So I did try changing my 2nd loop to for (int j=2; j<sqrt(i); j++) but it did not give me the result I needed.

How would I need to change this code to the way my book wants it to be?

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

        }   
    return 0;
}

A prime integer number is one that has exactly two different divisors, namely 1 and the number itself. Write, run, and test a C++ program that finds and prints all the prime numbers less than 100. (Hint: 1 is a prime number. For each number from 2 to 100, find Remainder = Number % n, where n ranges from 2 to sqrt(number). \ If n is greater than sqrt(number), the number is not equally divisible by n. Why? If any Remainder equals 0, the number is no a prime number.)

like image 877
Sahat Yalkabov Avatar asked Mar 05 '11 00:03

Sahat Yalkabov


3 Answers

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.

like image 151
ProdigySim Avatar answered Sep 18 '22 09:09

ProdigySim


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

like image 35
sth Avatar answered Sep 22 '22 09:09

sth


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.

like image 29
Jerry Coffin Avatar answered Sep 22 '22 09:09

Jerry Coffin