项目Euler 10th问题总和所有素数低于2kk [英] Project Euler 10th problem sum all primes under 2kk

问题描述

我正在尝试解决第10个项目的欧拉问题，即找到低于2kk的所有素数的总和。

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

#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;
}

但解决方案不正确，有什么帮助吗？



谢谢，Sam。

But The solution is not correct, any help ?

Thanks, Sam.

推荐答案

你所拥有的是数字溢出，你的代码逻辑是正确的，但你的long值可能是一个32位整数，其最大值是2,147,483,647，当前你是无符号的如果无符号4,294,967,295这两个值都小于142,913,828,922你需要的是至少一个38位整数，但下一个常见的整数类型是64位。如果将使用术语

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

long long

表示64位整数。这是常见的C ++ 11编译器。如果

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

long long

则使用任何类型complier用于表示64位整数。我只修复你的主要功能，因为其他一切看起来都正确。

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.

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>

这篇关于项目Euler 10th问题总和所有素数低于2kk的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！