Prime Numbers Up To A Number

Question

Im really new to C++ and im working through the book Programming: Principles and Practice Using C++. Were working on the problem to find all prime numbers between 1 - user given number. Now I got that part down. I now understand that the sqrt(i) would make the loop shorter but, Im not sure what to check for to see if its a prime or not in my if - else statements.

#include<vector>
#include<iostream>
#include<cmath>

using namespace std;

int main(){    
    vector<double> prime_numbers;
    double num;

    cout << "Please enter a number so we can find the primes for it: " << flush;
    cin >> num;

    for (int i = 2; i <= num; i++) {
        for (int j = 2; j <= i; j++) {
            // cout << sqrt(i) << "\t";

            // Check to see if Value of i is incremented correctly
            // Check to see if value of j is incremented properly before returnign to i
            //cout << i <<"\t" << j << endl;       

            if (j == i) {
                prime_numbers.push_back(i);
            }
            if (i % j == 0) {
                break;
            }   

        }   
    }
    for (double x : prime_numbers)
        cout << x << " | ";

    return 0;
}

Possible duplicate of [Why do we check up to the square root of a prime number to determine if it is prime?](https://stackoverflow.com/questions/5811151/why-do-we-check-up-to-the-square-root-of-a-prime-number-to-determine-if-it-is-pr) — ZiggZagg, Apr 28 '18 at 12:22
You're not finding any prime numbers. What makes you think that you "got that part down" when the loop that prints the primes doesn't print anything? (`j == i` is never true. Think about why for a few minutes.) — molbdnilo, Apr 28 '18 at 12:26
Look up the [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes). — eesiraed, Apr 28 '18 at 20:34

score 1 · Answer 1 · answered Apr 28 '18 at 12:55

1

A very efficient way to find the prime numbers from 0 to n is using the sieve of Eratosthenes, there are many ways to do it, here is an example:

vector<bool> v(n, true);
v[0] = v[1] = false;
for (int i = 2; i*i < n; i+= 2){
    if (v[i]) {
        for (int k = i*i; k < n; k += i) {
            v[k] = false;
        }
        if (i == 2)i = 1;
    }
}
for(auto i = 0; i < n; ++i)
      if(v[i])cout << i << ' ';
cout << endl;

answered Apr 28 '18 at 12:55

polmonroig

937
4
12
22

thanks @polmonroig ill have a look at this code for the next example ahah. They do ask us to use the sieve of Eratothenes as well. – Constant Furstenberg Apr 28 '18 at 13:03
Ok, I made it more complicated than it can be, but is more efficient. – polmonroig Apr 28 '18 at 13:08

score 1 · Answer 2 · answered Apr 28 '18 at 13:33

The difference is that your previous primality condition – i == j– is no longer true.

It is true exactly when you have examined every number from 2 to i, but with the sqrt(i) limit, you're exiting the loop much earlier.

I think the simplest change is to introduce a variable and move the push_back outside the loop (this works with either loop condition):

for (int i = 2; i <= num; i++) {
    bool isPrime = true;  // Assume 'i' is prime until proven wrong.
    for (int j = 2; j <= sqrt(i); j++) {
        if (i % j == 0) {
            isPrime = false;
            break;
        }   
    }
    if (isPrime) {
        prime_numbers.push_back(i);
    }
 }

That is, first decide whether something is the case, then do something with that information.
This is a useful design in very many cases.

For instance,It makes it much easier to move the primality check into a function:

bool isPrime(int x) { /* something */ }

// ...

for (int i = 2; i <= num; i++) {
    if (isPrime(i)) {
        prime_numbers.push_back(i);
    }
}

ok perfect so that makes sense with the bool variable. Could it be done without the bool variable? Why do we assume they are all primes? If we’re searching through all the numbers, why isn’t the if statement condition enough to then just add an else add to vector? — Constant Furstenberg, Apr 28 '18 at 14:24
@ConstantFurstenberg You only know it's prime if all the numbers you try aren't divisors, not just the first one. One number might not be an divisor, but you need the loop to continue to the next number since that might be a divisor. — eesiraed, Apr 28 '18 at 20:39

Prime Numbers Up To A Number

2 Answers2