求小于 2000000 的素数之和

Question

public static void main(String[] args) {
    int sum = 2;
    int isPrime;
    for(int x = 3; x < 2000000; x+=2){
        isPrime = 0;
        int y = 3;
        while(isPrime == 0) {
            if(x % y==0){
                isPrime = 1;
            }
            if(y > Math.ceil(x/2)) {
                isPrime = 1;
                sum+=x;
            }
            y += 2;
        }
    }
    System.out.println(sum);
}

上面的代码适用于 x < 1000，但我得到 x = 2000000 的错误答案，我无法理解原因。

Answer 1

是因为一个叫integer overflow的东西。简而言之，它指的是计算机中整数具有最大位数（即二进制数字）的概念。 int 最大为 32 位，这意味着在无符号系统中可能的最大数字是 2^32-1。如果您将 1 添加到该数字，您将得到 0，因为没有更多的数字可以承载 1!

因此，对于您的代码，请使用 long（具有 64 位限制）：

long sum = 2;
for(int i = 3 ; i < 2000000 ; i+=2) if(/*i is Prime*/) sum += i;
System.out.println(sum);

这里有一个 YouTube video 解释它是什么。

Answer 2

您的程序有 2 个问题，第一个问题由 @Malijam 指定，答案会溢出。

第二个是关于 O(n^2) 最坏情况的复杂性。操作太多了。

您可以稍微修改您的代码，通过检查小于候选数字平方根的因子来使其O(n * sqrt(n))，这样会更快。

修改后的代码：

public static void main(String[] args) {
    long sum = 2;
    long isPrime;
    for(int x = 3; x < 2000000; x+=2){//x is the number we check for if it is a prime
        isPrime = 0;
        long y = 3;
        while(isPrime == 0) {
            if(x%y==0){
                isPrime = 1;
            }
            if(y*y > x) {
                isPrime = 1;
                sum+=x;
            }
            y += 2;
        }
    }
    System.out.println(sum);
}

Ideone 演示：http://ideone.com/k1XAuA

Answer 3

int in Java 是一个 signed 数，其中最大可能值为 2³¹ - 1 . 由于您的最大值约为 200 万，因此您只需要 1000 多个这种大小的值，总和就会超过约 20 亿的限制。当超过这个限制时，int 类型保留最低的 32 位，而不是抛出错误，这看起来是一个正常的结果，但实际上是不正确的。

顺便说一句，您可以通过替换

来查看何时发生这种情况

sum+=x;

和

sum = Math.addExact(sum, x);

此检查溢出。

public static int addExact(int x, int y) {
    int r = x + y;
    // HD 2-12 Overflow iff both arguments have the opposite sign of the result
    if (((x ^ r) & (y ^ r)) < 0) {
        throw new ArithmeticException("integer overflow");
    }
    return r;
}

我建议使用有上限的 long ~ 90 亿。

顺便说一句，如果您需要所有素数达到已知限制，使用 Sieve of Eratosthenes 可能是更有效的解决方案。如果您想随机检查一个数字，则搜索数字的所有可能因素往往会更有效。

下面是我将如何编写您必须使用 long 并简化代码的方法。

public static void main(String... args) {
    long sum = 2;
    for(int x = 3; x < 2000000; x += 2) 
        if (isPrime(x)) 
           sum += x;

    System.out.println(sum);
}

/**
 * @param x is the number we check for if it is a prime
 */
static boolean isPrime(long x) {
    if (x % 2 == 0) 
        return false;
    for (int y = 3; y * y <= x; y += 2) 
        if (x % y == 0) 
            return false;
    return true;
}

Answer 4

你的代码似乎可以在我的电脑上运行。代码打印出 1179908154，这与 uSeemSurprised 的答案中显示的不同，但它应该给了你一个输出。算术程序花了很长时间（大约 2 分钟），但运行良好。根据您计算机的性能，这可能需要很长时间。

PS：我做了一些改动，使程序的运行时间不那么长。我转了

if(y > Math.ceil(x/2))

至

如果(y*3>x)

当您运行代码数百万次时，调用 Math.ceil 确实效率低下。我认为乘法也比除法快。我还将 int y 的声明移到了 for 循环之外。结果代码的速度是原来的三倍。

Answer 5

笼统的回答：你和通过下面的代码找到一些直到n的所有质数：

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
   long long int tc,N;
    unsigned long long int sum=0;
   vector <long long int>v;
    long long int arr[1000000] = {0},i,j;
    for (i = 2; i < 1000000; i++)
    {
        for ( j = i * i; j < 1000000; j+=i)
        {
            arr[j - 1] = 1;
        }
    }
    for (int i = 1; i < 1000000; i++)
    {
        if (arr[i - 1] == 0)
            v.push_back(i);
    }
       cout<<"\nEnter the number:";
       cin>>N;
       i=1;
       while(v.at(i)<=N)
       {
           sum+=v.at(i);
           i++;
       }
       cout<<sum<<"\n";
       sum=0;

   return 0;
}

求小于 2000000 的素数之和

Finding sum of primes below 2000000

java

integer-overflow