Prime Printer won't print primes. Prints everything instead

Question

I have no idea what I'm doing wrong, here is the code:

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

//vector<int> primes;

bool isPrime(int c, vector<int> p){
    for(int i = 0; i<p.size(); i++){
        int prime = p[i];
        if(prime*prime > c) return true;
        if(c%prime == 0) return false;
    }
}

int main(int argc, char *argv[])
{
    vector<int> primes;
    primes.push_back(2);
    for(int n = 3; n>1; n++){
        if(isPrime(n, primes)){
            primes.push_back(n);
            cout << n << endl;
         }//else cout << "no" << endl;
    }
    return 0;
}

Is there anything specific causing the problem? Because it shouldn't be printing every number.

`for(int n = 3; n>1; n++)`? That looks odd. What do you mean to do here? — cigien, Jun 23 '20 at 18:07
How your `isPrime` is supposed to work? Can you describe the algorithm? — Eugene Sh., Jun 23 '20 at 18:08
The for loop didn't need a conditional, but if there was an integer overflow or something that would hopefully make it stop, it starts at 3 because I added 2 already. — Dead beat, Jun 23 '20 at 18:11
You should not rely on the program crashing as a method to stop a loop. — drescherjm, Jun 23 '20 at 18:13
If your `int` overflows, then you have undefined behaviour, see https://stackoverflow.com/questions/16188263/is-signed-integer-overflow-still-undefined-behavior-in-c. — Werner Henze, Jun 23 '20 at 18:15
As for how isPrime works: basically it runs through each prime, if a prime's square is greater than the number, then you should have already found another prime that the number is divisible by but if you haven't then the number must be prime, otherwise check if the number is divisible by the prime and if it is then it can't be a prime. — Dead beat, Jun 23 '20 at 18:18
I just ran your program here. It prints all the primes and nothing else -> voting to close. — Werner Henze, Jun 23 '20 at 18:18
Your code is fine, just fix the test condition of for loop and prevent it from being infinite. code gave correct results when I fixed it. — Captain Levi, Jun 23 '20 at 18:21
One improvement is to not pass the primes by value. [https://ideone.com/BaqS8R](https://ideone.com/BaqS8R) — drescherjm, Jun 23 '20 at 18:23

score 2 · Answer 1 · answered Jun 23 '20 at 18:14

It probably must be going into infinite loop. for(int n = 3; n>1; n++) must be - for(int n = 3; n<upper_limit; n++), where upper_limit is the max number upto which you want to print primes. The below code works -

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

//vector<int> primes;

bool isPrime(int c, vector<int> p){
    for(int i = 0; i<p.size(); i++){
        int prime = p[i];
        if(prime*prime > c) return true;
        if(c%prime == 0) return false;
    }
}

int main(int argc, char *argv[])
{
    vector<int> primes;
    primes.push_back(2);
    for(int n = 3; n<10; n++){
        if(isPrime(n, primes)){
            primes.push_back(n);
            cout << n << endl;
         }//else cout << "no" << endl;
    }
    return 0;
}

You program works as well...just that it prints primes forever until the memory runs out and it crashes (probably not what you want :) ). So, add a stop condition and it would run fine.

Thank you, I didn't realize that it would crash before displaying an output, at least on my device. — Dead beat, Jun 23 '20 at 18:26
Side note: Can save a bunch of copying by passing `p` by `const` reference. — user4581301, Jun 23 '20 at 18:37
`prime*prime > c` is prone to overflow when `c` is a prime near `INT_MAX`. `if(prime > c/prime) return true;` fixes that at little cost as `c/prime` and `c%prime` often use shared code. — chux - Reinstate Monica, Jun 23 '20 at 23:19

Prime Printer won't print primes. Prints everything instead

1 Answers1