C++ Prime Numbers program

Question

I'm working on a C++ program that determines and prints the prime numbers between 3 and an integer 'x' the user inputs. I'm assuming that I need a double nested loop for this, one to iterate from 3 to x and the other to check if the number is prime. I think it needs to do something like go from 2 to x-1? I'm just really not sure how to do this syntax-wise. Thanks for any help! :)

EDIT: This is what I have:

#include <iostream>
#include <cmath>

using std::cout;
using std::endl;
using std::cin;

int main(){

   int x;
   int i;
   int j;

   cout << "Please enter an integer 'x' greater than 3: " << endl;

   cin >> x;

   if (x <= 3){

        cout << "Please enter new value 'x' greater than 3: " << endl;

        cin >> x;
   }
        for(int i=3; i<=x; i++){
                for(j=2; j<i; j++){
                   if(i%j == 0)
                        break;
                   else if(i == j+1);
                        cout << i << endl;
                   }
        }
        return 0;
}

And I when I enter 10 as 'x' I get the output: 3 5 5 5 7 7 7 7 7 9

Can anyone tell me how to fix this?

Answer 1

Provided your X is small enough, you can use the Sieve of Eratosthenes to do it more efficiently. This is ideal for the "primes up to X" case since it maintains a memory of previously discarded primes. It does so by keeping a set of flags for each candidate number, all initially set to true (except for 1, of course).

Then you take the first true value (2), output that as a prime, and then set the flags for all multiples of that to false.

Then carry on with:

• 3;
• 5 (since 4 was a multiple of 2);
• 7 (since 6 was a multiple of 2 and 3);
• 11 (since 8 and 10 were multiples of 2 and 9 was a multiple of 3);
• 13 (since 12 was a multiple of 2);
• 17 (since 14 and 16 were multiples of 2 and 15 was a multiple of 3 and 5);
• and so on.

Pseudo-code would be similar to:

def showPrimesUpTo (num):
    // create array of all true values

    array isPrime[2..num] = true

    // start with 2 and go until finished

    currNum = 2
    while currNum <= num:
        // if prime, output it

        if isPrime[currNum]:
            output currNum

            // also flag all multiples as nonprime

            clearNum = currNum * 2
            while clearNum <= num:
                isprime[clearNum] = false
                clearNum = clearNum + currNum

        // advance to next candidate

        currNum = currNum + 1

Otherwise, you can do trial division as per your suggestion. The basic idea is to check each number from 2 up to the square root of your target number to see if it's a multiple. In pseudo-code, that would be something like:

def isPrime (num):
    // val is the value to check for factor

    val = 2

    // only need to check so far

    while val * val <= num:
        // check if an exact multiple

        if int (num / val) * val == num:
            return false

        // no, carry on

        val = val + 1

    // if no factors found, it is a prime

    return true

The reason you only need to check up to the square root is because, if you find a factor above there, you would have already found the corresponding factor below the square root.

For example, 3 x 17 is 51. If you're checking the numbers from 2 through 50 to see if 51 is prime, you'll find 3 first, meaning you never need to check 17.

Answer 2

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

            }

        }   

    return 0;
}

Printing prime numbers from 1 through 100 Basically this, but modified

Answer 3

I find this one pretty fast and efficient

 int main(){
    for(int i=3; i<=X; i++)    
            if(IsPrime(i)){
               cout<<i<<endl;
            }
    }

 bool IsPrime(int num){
    /* use commented part if want from 2
        if(num<=1)

            return false;

        if(num==2)

            return true;
    */
        if(num%2==0)

            return false;

        int sRoot = sqrt(num*1.0);

        for(int i=3; i<=sRoot; i+=2)

        {

            if(num%i==0)

                return false;

        }

        return true;
    }