# Thread: Prime number check

1. ## Prime number check

I'm making a program that is supposed to get the sum of all prime number in a specified range which is in this case 1 000 000. The program works fine, except that it seems to count some prime numbers even if they aren't prime.

Here is my code:
Code:
```#include <iostream>
#include <cmath>

using namespace std;

const int RANGE = 1000000;

bool isPrime(int n) {
if (n <= 0 || n == 1 || (n % 2 == 0 && n != 2))
return false;

for (int i=3;i<sqrt(n);i++) {
if ((n%i) == 0)
return false;
}
return true;
}

int main(void) {
unsigned long sumPrimes = 0;
long counter = 0;

for (int i=0;i<RANGE-1;i++) {
if (isPrime(i)) {
cout << i << endl;
sumPrimes+=i;
counter++;
}
}

cout << "Counter: " << counter << endl;
cout << "Sum of primes: " << sumPrimes;

while (cin) cin.get();
return 0;
}```
I'm fairly certain that the isPrime() function is wrong, since the actual prime count should be somewhere closer to 78000. My program counts exactly: 78665 when the range is 1 000 000. It works fine when I take a lower range. Any ideas/improvements?

2. Hmmm...
And what will your function return for 9? or 25? true or false?

3. True for both.. so why does it return true for them? I searched around for hours and found out that it's even enough to check if it's divisible with any number until the square root of the checked number. In other words the following code was considered enough:

bool isPrime(int n) {
for (int i=3;i<sqrt(n);i++) {
if ((n&#37;i) == 0)
return false;
}
return true;
}

edit: It was because it was supposed to be sqrt(n)+1 instead of sqrt(n). It doesn't return true on number 9 and 25 now, but the main problem still remains.

4. Originally Posted by password
True for both.. so why does it return true for them?
Because you should be looping while "<= sqrt(n)" not just "< sqrt(n)". If the number is square, then sqrt(n) is a factor, but you never check it.

Popular pages Recent additions