Calculate the sum of all the primes below two million.

Question

1.67/5 (3 votes)

See more:

Hi I want to calculate the sum of all primes bellow two milion and this is my code but the result is not valid what's the problem

C++

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

using namespace std;

int main() {

int sum=2;

int s;
for ( s=3;s<20;s+=2)
{
    bool is_prime = true;

    for (int i = 2; i <= sqrt(s); i++)
    {

        if (s % i == 0)
            is_prime = false;
    }
    if (is_prime)
    {

        sum=sum+s;

    }


}
cout <<sum;


return 0;
}

Posted 11-Jul-12 5:37am

sadegh_sh

Add a Solution

Comments

Richard MacCutchan 11-Jul-12 12:37pm

the result is not valid
OK, you need to tell us what result you expect, and what result you get. Alternatively, you could step through the code with your debugger to find out what interim values your code is producing.

Sergey Alexandrovich Kryukov 12-Jul-12 10:35am

Well, we all know what result do we expect, don't we? :-)
Of course, it's hard to expect a lot of enthusiasm in running this code and testing...
I think the answers by Stefan and myself are more adequate...
--SA

2 solutions

Solution 2

1. If you don't know what's wrong, cut your problem into smaller ones! In this case (a) verify that the primes you calculate are indeed (all the) primes. (e. g. print the first ones) And (b) verify that your sum is calculated correctly (e. g. print the first few intermediate results)

Note: a better method than printing is to use the debugger and inspect the values of your variables throughout your first couple of iterations. That way you don't have to modify your code and don't risk accidentally breaking it.

2. Make an estimation of the expected result, or get the actual value if you can. Then compare it against your result: is it off by just a small difference? Is it more like a factor of 2, or 20, or 50? Or is it completely off?

Depending on what you see there may be quite different causes:
- in the first case it may be related to your initialization, how you start your loop, or how you end your loop;
- in the second case I really can't say, but you should see that deviation in early iterations, so go back to step 1 and use a debugger;
- in the last case, you may have run into a numerical limitation, e. g. an integer overflow: try using long or long long instead of int for sum, or if that doesn't work, try double. (note: your compiler may not support long long)

Posted 11-Jul-12 22:49pm

Stefan_Lang

Comments

Sergey Alexandrovich Kryukov 12-Jul-12 10:37am

Well, yes, nice advice.
I only disagree in last paragraph: double is not adequate, as it represent approximated numbers. For precise calculations with big integer numbers, System.Numerics.BigInteger should be used. This type is absolutely great code, by the way. So, I voted 4.
--SA

Stefan_Lang 12-Jul-12 11:05am

I only suggested double as a last resort, in case the compiler doesn't support a greater than 32 bit integer type.

In fact a double will be enough: The sum of all numbers up to 2 million is:

sum(all < 2000000) = 2000000*1999999/2 ~ 4*10^12

That is less than 2^42, so can be expressed in only 42 bit (43 if you add one for the sign). That's less than a double has available for the mantisse alone, so that number will in fact be represented exactly!

A bit more realistic estimate for the result is an average value of 1000000 for each prime, and assume only about 10-20% of all numbers to be prime, then the result should be about this:

sum(primes < 2000000) ~= 1000000 * (10-20% * 2000000) = 2-4 * 10^11

That requires about 37-39 bits. Still too much for a 32 bit number, but can be easily stored in a double. (or 64 bit long if you have that)

I agree about Biginteger, but it's not standard C++ and I didn't want to make any assumptions about the auhtors ability to install and use additional libraries.

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Sergey Alexandrovich Kryukov · Accepted Answer · 2012-07-11T05:52:00

This is not simple, this is a very simple task. If you cannot solve it fully by yourself, your further learning can be pretty much useless. You need something, some minor success, to start trusting your own capabilities. Start with this very simple task. Proof to yourself you are good for something, and can solve at least some problems without any help, all on your own. This is one of the pretty good exercises for the beginners, will let you feel how programming works. Don't miss this chance to learn something. And do not screw up this valuable chance by asking someone to help you. Don't underestimate the value of it.

One — very introductory — advice: from the very beginning, learn how to make one step at a time. Ever heard about separation of concerns? Try to separate concerns as much as you can, especially at first. In this case, make a separate function IsPrime(unsigned int). (Use unsigned int, or unsigned long, not int, learn to choose adequate types.) And a separate function for finding a sum. At first steps, separation of concerns, readability and explicit expression of the ideas should be your first priority. Optimization will come later. (And this task will execute very quickly anyway.)

Good luck,

—SA