Prime Numbers

• Question

• I know that this may not be the fastest way to solve find the sum of all prime numbers under 2000000 but I dont understand why it is not working

```#include "stdafx.h"
#include <iostream>
#include <cmath>
using namespace std;

int main()
{
int isPrime;
int total = 0;
for(int i=1;i<2000000;i++)
{
for(int j=2;j<i;j++)
{
isPrime = i % j;
if (isPrime == 0)
{
if (isPrime == j)
{
total += i;
break;
}
break;
}
}
}
cout << total << endl;
system("pause");
return 0;
}```

Saturday, July 4, 2009 1:27 AM

• What does this accomplish?

if (isPrime == 0)
{
if (isPrime == j) // means: if(j == 0)

Since j can never be less than 2 ...

- Wayne

• Marked as answer by Friday, July 10, 2009 3:40 AM
Saturday, July 4, 2009 2:27 AM
• You are going to have to write a functional prime generator first.  The algorithm is over 2000 years old.
Hans Passant.
• Marked as answer by Friday, July 10, 2009 3:39 AM
Saturday, July 4, 2009 11:41 AM

All replies

• Quote>I dont understand why it is not working

What does that mean *exactly*?

It gives non-primes? It gives nothing? It gives only some primes? Other?

- Wayne
Saturday, July 4, 2009 2:15 AM
• I am sorry for being so ambiguos.

There is no visibile pattern to me, below are the first few numbers that it outputs in the first if.
4
6
8
9
10
12
14
15
16
18
20
21
22
24
25
26
27
28

It does not give anything for the second if statement.

Saturday, July 4, 2009 2:26 AM
• What does this accomplish?

if (isPrime == 0)
{
if (isPrime == j) // means: if(j == 0)

Since j can never be less than 2 ...

- Wayne

• Marked as answer by Friday, July 10, 2009 3:40 AM
Saturday, July 4, 2009 2:27 AM
• Thank you for noticing that :)
But even if I change it to
if (i==j)

At the end there is no output
Saturday, July 4, 2009 2:48 AM
• Of course not. That makes no sense.

Perhaps you should describe in words what a prime number is, and then write out in pseudo-code how to determine a prime number.

There is no point in just coding it for you, otherwise you don't learn.
Saturday, July 4, 2009 3:06 AM
• Quote>if (i==j)

How can this ever be true inside a for loop which only executes while j is less than i?

- Wayne
Saturday, July 4, 2009 3:07 AM
• I may not be answering your question but a couple of points to make the search faster. You don't have to check till the number (2000000). It's just enough to check till the square root of 2000000. In the inner loop you first check if it is divisible by 2 and then check with odd numbers only like 3, 5, 7 etc.
«_Superman_»
Saturday, July 4, 2009 3:54 AM
• This is what I am trying to do.

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

Saturday, July 4, 2009 3:59 AM
• You are going to have to write a functional prime generator first.  The algorithm is over 2000 years old.
Hans Passant.
• Marked as answer by Friday, July 10, 2009 3:39 AM
Saturday, July 4, 2009 11:41 AM
• A simplifying strategy here would be to write a separate function to test for prime-ness.

bool IsPrime(int i);

int main()
{
int total = 0;
for(int i=1;i<2000000;i++)
{
if (IsPrime(i))
{
total += i;
}
cout << total << endl;
return 0;
}

bool IsPrime(int i)
{