-
Fresh Eyes, Please
This is actually for Project Euler (Probably shouldn't be asking for help, but I want to know). I'm trying to find the sum of all prime numbers less then 1,000,000. So, I was just trying to brute force it. I've read over the code a million times, but I can't figure out whats going on.
It's returning a crazy negative number. -1104303641 to be specific.
Code:
#include <iostream>
#include <vector>
using namespace std;
bool check_prime(int &num);
int main()
{
int total = 2; //Start at 2, because the loop starts with 3, so still needs to be accounted for.
for (int c = 3; c < 1000000; c += 2) //Increment by 2, because primes are odd.
{
if (check_prime(c))
{
total += c;
}
if (c % 729 == 0) //Get a % completion.
{
system("clear");
cout << (c / 1000000.0f) * 100.0f << "%" << endl;
}
}
cout << "done" << endl;
cout << "Total: " << total << endl;
return 0;
}
/*
Checks if the number given is prime...I hope.
*/
bool check_prime(int &num)
{
for (int k = 2; k < num; ++k)
{
if (num % k == 0)
{
return false;
}
}
return true;
}
It's very slow too. If you want to compile it you can change 'system("clear")' to what ever you like, or just take it out altogether. So, my main question is, "Why is the total coming out negative?"
Thanks
-
probably - you have overflow
change total to double to check it...
And about more optimal prime number search algorithm - search the forum, it was discussed several times
-
I'm guessing that your sum is exceeding the maximum value of an int (consider that the number of primes less than a given number N is roughly N/ln(N), by the Prime Number Theorem, and you could make a ballpark guess as to what the sum should be). BTW, using Eratosthenes' sieve would compute the primes much faster. There was a thread on this a while back.
http://mathworld.wolfram.com/PrimeNumberTheorem.html
Edit: http://cboard.cprogramming.com/showthread.php?t=91461
-
Oh, thanks for the link. I'll try double and let you know how it works.
-
Alright, well that fixed the problem. Still not getting the right answer. I got 37,550,400,000 o_0
So I'm going to redo it I think.
Thanks for you help,
David
-
If you want to use system("clear") you must have #include <stdlib.h>.