Implementing a prime number counter

Question

For some reason, my last prime(int prime) isn't showing up at the end. Any clue ? fyi: primeEval stands for a flag, if the loop ends && primeEval==2, the number is actually a prime number. qty stands for quantity of primes counted.

int main(){


long primeEval=0,prime=0,qtyprime=0;

time_t timerr=(time(NULL)+10);



   for (int i = 2; time(NULL)!=timerr; i++) {

        for (int j = 1; j <= i; j++) {

            if((i%j)==0 && primeEval<2){

                primeEval++;

                if (i==j && primeEval==2) {
                    qtyprime++;
                    prime=i;
                    primeEval=0; // Resets for the next number 'i'

                }
            }

        }
    }

cout << "last prime found: " << prime << endl << "Ttal primes found: " << qtyprime;
}

you could easily improve performance by changing `j <= i` to `j <= sqrt(i)`. This would enforce more changes, but it would run faster — shapiro yaacov, Jun 11 '15 at 14:42
What do you mean it's not showing up? Like it's giving the wrong number? not printing at all? — Olivier Poulin, Jun 11 '15 at 14:43
@OlivierPoulin The output is: last prime found: 2 Ttal primes found: 45190040 — sayajeans, Jun 11 '15 at 14:45
Also, once you've found a number `y=i%j`, why continue the inner loop? finish it immediately and move on to the next number. — shapiro yaacov, Jun 11 '15 at 14:46
@shapiro.yaacov to be a prime number, must be only divided by itself and 1, primeEval gets 2 flags to indicate that's prime. — sayajeans, Jun 11 '15 at 14:49
Why are you only checking even numbers? Shouldn't you find more prime numbers if you look at the odd numbers? — Werner Henze, Jun 11 '15 at 14:56
Why do you only reset primeEval when you found a prime number? — Werner Henze, Jun 11 '15 at 14:57

score 2 · Accepted Answer · edited May 23 '17 at 12:30

New Answer:

With the change in your code you will now loop through all number. The problem with it now is that once you find a non prime number you will never reset primeEval and because of that you will never capture another prime number If you change your code to the following it will work

int main()
{
    long primeEval = 0, prime = 0, qtyprime = 0;
    time_t timerr = (time(NULL) + 10);

    for (int i = 2; time(NULL) != timerr; i++) {

        for (int j = 1; j <= i; j++) {

            if ((i%j) == 0){
                primeEval++;  // incmrent factor
            }
            // if we are at the end and have 2 factors then we are prime
            if (i == j && primeEval == 2) {
                qtyprime++;
                prime = i;
                primeEval = 0; // Resets for the next number 'i'
            }
            // if we reach the end with more than 2 factors reset and go to the next number
            if (i == j && primeEval > 2) {
                primeEval = 0; // Resets for the next number 'i'
            }
        }
    }
    cout << "last prime found: " << prime << endl << "Ttal primes found: " << qtyprime;
    cin.get();
    return 0;
}

I would also suggest you look at Which is the fastest algorithm to find prime numbers? to find some more efficient ways to get prime numbers.

Old Answer:

In your code you have:

for (int i = 2; time(NULL)!=timerr; i=+2)

So when you start checking from primes you start with 2 which is prime. Then you increment i by 2 so the next number you check is 4 which is an even number. All even numbers are not prime except for 2. Since you are always adding 2 you will always have an even number so the only prime number you will find is 2.

It was a old implementation(to only check odd numbers) that i forgot to correct, but its i++ instead of i+2. — sayajeans, Jun 11 '15 at 14:57
"Then you increment i by 2 so the next number you check is 4 which is an even number": Now OP has explained it's a typo and he wanted to write `i++`, but since he wrote `+=` instead of `=+`, what he was actually doing was setting `i` to +2, every time. — Fabio says Reinstate Monica, Jun 11 '15 at 15:06
Argh, damned typos! What I meant is: he wrote `=+` instead of `+=`. — Fabio says Reinstate Monica, Jun 11 '15 at 15:15

Fabio says Reinstate Monica · Answer 2 · 2015-06-11T15:11:32.930

You have different issues:

for (int i = 2; time(NULL)!=timerr; i=+2) {

Here the syntax is just wrong: it must be i+=2, not i=+2, otherwise you will keep setting i to +2 and testing whether 2 is prime.

Then, as others have pointed out, why are you increasing i by 2? If you want to optimize the search, you should increase j by 2, not i! And j should in any case start from 2 (or, given your approach, from 1), and then you should try j = 3 and then you can increase j by 2 without the risk of skipping some important divisors.

Then, you reset primeEval to 0 only if you find a prime. If you test a number i that is not prime, primeEval stays at 2 and you'll never get into the block again.

So the final code could be:

#include <iostream>
using namespace std;

int main(){

    long primeEval=0,prime=0,qtyprime=0;

    time_t timerr=(time(NULL)+10);

    for (int i = 2; time(NULL)!=timerr; i++) {
        primeEval=0;
        for (int j = 1; j <= i; j++) {
            if((i%j)==0 && primeEval<2){
                primeEval++;
                if (i==j && primeEval==2) {
                    qtyprime++;
                    prime=i;
                    primeEval=0; // Resets for the next number 'i'
                }
            }
        }
    }

    cout << "last prime found: " << prime << endl << "Ttal primes found: " << qtyprime;
}

Implementing a prime number counter

2 Answers2