Project Euler 10th problem sum all primes under 2kk

Question

1.00/5 (1 vote)

See more:

Hi, I'm trying to solve the 10th project euler problem of finding the summation of all prime numbers below 2kk .

C++

#include <iostream>
#include <vector>

using namespace std;

struct pr
{
    long num;
    bool is_prime;
};

vector<pr> getPrime(long n)
{
    vector<pr> my_prime(n+1);
    for (long i = 0; i <= n; i++)
    {
        my_prime[i].num = i;
        my_prime[i].is_prime = true;
    }
    my_prime[0].is_prime = false;
    my_prime[1].is_prime = false;
    long p = 2;
    while ( (p*p) <= n )
    {
        for (long i = 2; i*p <= n; i++)
        {
            my_prime[i*p].is_prime = false;
        }
        for (long j = p + 1 ; j <= n; j++)
        {
            if (my_prime[j].is_prime == true)
            {
                p = my_prime[j].num;
                break;
            }
        }
    }
    return my_prime;
}

int main()
{
    vector<pr> p = getPrime(1999999);
    long counter = 0;
    for (vector<pr>::iterator itr = p.begin(); itr != p.end(); ++itr)
    {
        if ( (*itr).is_prime == true )
            counter += (*itr).num;
    }
    cout << counter;
}

But The solution is not correct, any help ?

Thanks, Sam.

Posted 21-Jun-15 9:22am

Samuel Shokry

Add a Solution

Comments

PIEBALDconsult 21-Jun-15 15:26pm

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Samuel Shokry 21-Jun-15 15:59pm

I used it in my code

PIEBALDconsult 21-Jun-15 15:27pm

P.S. Is _one_ prime?

Dave Kreskowiak 21-Jun-15 16:28pm

I can tell you that my Sieve of Eratosthenes doesn't look anything like yours. For starters, my 0 and 1 values start out as Prime whereas yours don't.

Why are you using an array of structures where you have the value and a flag? Why not just have an array of flags? The value is the index into the array!

Oh, my "flag" is actually an enum that provides each value with one of 3 states, not 2.

PIEBALDconsult 22-Jun-15 0:39am

I use a long integer to contain sixty-four flags, and those flags are only for the odd numbers, so I really pack the values together and extend my range.

Samuel Shokry 22-Jun-15 9:07am

I used long long int instead of long and it worked for me :)

Stefan_Lang 24-Jun-15 3:56am

Then 2kk clearly wasn't a typo meaning 2k=2000, but a typo meaning a much bigger number. Maybe you should be clearer about your problem next time you ask.

Also, as has been indicated, "not correct" is not a valid problem description - if you had stated "My result for summing up the first 2000 primes is x, but it is supposed to be y", then this would have been a much clearer indication of what you tried to do. Better yet, if you had tried your algorithm with a smaller number, you could already have gotten yourself and us an extremely useful information.

Please, next time you post a question, put a little more effort into describing what, exactly, does not produce the expected result, what you tried, the result you expect, the result you get, etc.. And don't use non-standard abbreviations that can lead to amiguities and misunderstanding, such as 2kk

Samuel Shokry 24-Jun-15 8:42am

I would work hard the next time

1 solution

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)

vickoza · Answer 1 · 2015-07-13T08:32:00

what you have is numeric overflow the logic of you code is right but your long value probably is a 32-bit integer whose max value is 2,147,483,647 unsigned as you currently have and if unsigned 4,294,967,295 both values are less than 142,913,828,922 what you need is at least a 38-bit integer but the next common integer type is 64-bit. If will use the term

C++

long long

to represent a 64-bit integer. This is common is C++ 11 complier. If

C++

long long

then uses whatever type you complier uses to represent a 64-bit integer. I will only fix your main function as everything else look right.

C++

int main()
{
    vector<pr> p = getPrime(1999999);
    long long counter = 0;
    for (vector<pr>::iterator itr = p.begin(); itr != p.end(); ++itr)
    {
        if ( (*itr).is_prime == true )
            counter += (*itr).num;
    }
    cout << counter;
}
</pr></pr>