为什么我的欧拉计划 #10 失败了？

发布于 2024-08-16 22:30:50 字数 712 浏览 4 评论 0原文

问题是：求200万以下所有素数的和。

我几乎做了埃拉斯托尼筛法，下面的程序似乎适用于小数，即定义 LIMIT 为 10L 产生 17 作为答案。

我提交了 1179908154 作为答案，由以下程序生成，但它不正确。

请帮忙指出问题所在。谢谢。

#include <stdio.h>

#define LIMIT 2000000L
int i[LIMIT];

int main()
{
    unsigned long int n = 0, k, sum = 0L;
    for(n = 0; n < LIMIT; n++)
        i[n] = 1;
    i[0] = 0;
    i[1] = 0;

    unsigned long int p = 2L;

    while (p*p < LIMIT)
    {
        k = 2L;
        while (p*k < LIMIT)
        {
            i[p*k] = 0;
            k++;
        }
        p++;
    }

    for(n = 0; n < LIMIT; n++)
        if (i[n] == 1)
        {
            sum += n;
        }
    printf("%lu\n",sum);

    return 0;
}

原文

Question is: Find the sum of all the primes below 2 million.

I pretty much did the Sieve of Erastothenes thing, and the program below seems to work for small number i.e. define LIMIT as 10L produces 17 as answer.

I submitted 1179908154 as the answer, as produced by the following program, and it was incorrect.

Please help pointing out the problem. Thanks.

#include <stdio.h>

#define LIMIT 2000000L
int i[LIMIT];

int main()
{
    unsigned long int n = 0, k, sum = 0L;
    for(n = 0; n < LIMIT; n++)
        i[n] = 1;
    i[0] = 0;
    i[1] = 0;

    unsigned long int p = 2L;

    while (p*p < LIMIT)
    {
        k = 2L;
        while (p*k < LIMIT)
        {
            i[p*k] = 0;
            k++;
        }
        p++;
    }

    for(n = 0; n < LIMIT; n++)
        if (i[n] == 1)
        {
            sum += n;
        }
    printf("%lu\n",sum);

    return 0;
}

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

秋千易 2024-08-23 22:30:50

您正确计算了素数，但总和太大（超过 2^32）并且不适合无符号 32 位长。您可以使用 64 位数字（在某些编译器上为 long long）来解决此问题。

回复收藏 0 原文

趴在窗边数星星i 2024-08-23 22:30:50

您的逻辑似乎是正确的，但您弄乱了数据类型及其范围。检查这是否有效：

#include <stdio.h>

#define LIMIT 2000000
int i[LIMIT];

int main()
 {
   long long int n = 0, k, sum = 0;
  for(n = 0; n < LIMIT; n++)
    i[n] = 1;
  i[0] = 0;
  i[1] = 0;

  long long int p = 2;

  while (p*p < LIMIT)
  {
    k = 2;
    while (p*k <LIMIT)
    {
        i[p*k] = 0;
        k++;
    }
    p++;
  }

  for(n = 0; n < LIMIT; n++)
    if (i[n] == 1)
    {
        sum += n;
    }
  printf("%lld\n",sum);

  return 0;
}

Output :142913828922

Your logic seems to be correct, but you are messing up with the data types and their ranges.Check whether this works or not:

#include <stdio.h>

#define LIMIT 2000000
int i[LIMIT];

int main()
 {
   long long int n = 0, k, sum = 0;
  for(n = 0; n < LIMIT; n++)
    i[n] = 1;
  i[0] = 0;
  i[1] = 0;

  long long int p = 2;

  while (p*p < LIMIT)
  {
    k = 2;
    while (p*k <LIMIT)
    {
        i[p*k] = 0;
        k++;
    }
    p++;
  }

  for(n = 0; n < LIMIT; n++)
    if (i[n] == 1)
    {
        sum += n;
    }
  printf("%lld\n",sum);

  return 0;
}

Output :142913828922

回复收藏 0 原文