5

我的代码粘贴在下面。当我运行这个程序时，它一直在计算。我使用的是旧的 Turbo C++ 编译器。这样的程序需要多长时间才能执行？我等了大约 5 分钟，但没有任何输出。

/*The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.
*/
#include<stdio.h>
#include<conio.h>
#define TWO_MILLION 2*1000*1000
int IsPrime(long unsigned int num);
int main()
{
    long unsigned int i,sum=0;
    clrscr();
    for(i=2;i<TWO_MILLION;i++)
    {
        if(IsPrime(i))
        sum+=i;
    }
    gotoxy(25,25);
    printf("%ld",sum);
    getch();
    return 0;
}
int IsPrime(long unsigned int num)
{
    int flag=1;
    long unsigned int i;
    for(i=2;i<num;i++)
    {
        if(num%i==0)
        {
            flag=0;
            break;
        }
    }
    return flag;
}
4

10 回答 10

21

您不是在进行数百万次计算，而是在进行数万亿次计算。

IsPrime 将在 O(n) 时间内运行，也就是说，它将执行 200 万条指令来确定单个数字。做这样的事情需要两百万的时间太长了。

要做到这一点，你真的想使用类似的东西：http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes，它可以更有效地确定特定范围内的所有素数。

于 2010-10-04T02:44:39.350 回答
3

执行这样的程序需要多少时间？

这完全取决于您的平台。我怀疑因为您正在执行 ~(200 万)^2 次操作 (~4 万亿) 计算，所以很长一段时间。

有更好的方法来执行你正在做的事情——例如，要检查素数，你只需要检查数字的平方根，而不是一直到数字本身。更不用说可能有一个动态编程解决方案可以比这快得多。

于 2010-10-04T02:40:17.137 回答
3

正如其他人所说，这将需要很长时间。另一种有趣的方法是埃拉托色尼筛法。你可以阅读它：

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

基本上，您使用数字 2...2 百万初始化一个数组。尚未处理的最小数字是素数。然后，从数组中删除该数字的所有倍数并继续。它会比你拥有的运行得快得多。

于 2010-10-04T02:48:33.870 回答
3

别出心裁的回答

gotoxy(25,25);

您是否以文本模式运行程序？如果文本屏幕只有80 x 25，并且如果第 25 行被其他东西遮挡，那么您很可能不会在文本屏幕中看到任何变化。

于 2010-10-04T02:52:00.180 回答
2

正如其他人所说：检查实施的限制

如果TurboC++有 <limits.h>，则那些实现限制在该标头中定义了相应的宏

#include <limits.h>
#include <stdio.h>
int main(void) {
    printf("int goes from %d to %d.\n", INT_MIN, INT_MAX);
    printf("long goes from %ld to %ld.\n", LONG_MIN, LONG_MAX);
    return 0;
}

如果失败，您需要自己“计算”限制。我正在切换，unsigned因为它们没有溢出问题，我只需要“计算”上限（下限为0）

#include <stdio.h>
int main(void) {
    unsigned u;
    unsigned long lu;

    u = -1; lu = -1;
    printf("unsigned ints go all the way to %u\n", u);
    printf("unsigned longs go all the way to %lu\n", lu);
    return 0;
}

在我的系统上，第一个程序输出

int 从 -2147483648 变为 2147483647。
long 从 -9223372036854775808 到 9223372036854775807。

和第二个程序输出

无符号整数一直到 4294967295
unsigned longs 一直到 18446744073709551615
于 2010-10-04T08:20:02.623 回答
2

除了“史诗”之外，仍然没有关于常数的评论/答案......

#define TWO_MILLION 2*1000*1000

这是不好的。当您稍后更改该值时，您可能会遇到名称内容不匹配：

#define TWO_MILLION 5*1000*1000

或者您将其重命名为

#define FIVE_MILLION 5*1000*1000

并且需要在您使用过它的任何地方进行更改。不要在内容之后命名你的常量，这只会把你的幻数变成幻名。以它们的含义命名它们，例如MAX_NUMBER UPPER_LIMIT RANGE_TO_TEST或任何最合适的名称。

于 2010-10-04T08:56:17.753 回答
1

您也可以使用筛方法来做到这一点，这并不比您使用的复杂得多。这个想法是选择前 n 个连续的素数并用它们来构造一个筛子。我在回答另一个问题时讨论了它（带有证明），Sheldon L. Cooper 在他的. 我认为他这样做没有得到足够的支持（我已经得到了“很好的答案”，所以也许你可以帮助他解决这个问题。

所以在你计算出筛子数之后，你只需要通过与筛子对齐并且小于 的平方根的数来测试可分性n。

于 2010-10-04T03:20:28.430 回答
0

这可能需要很长时间才能运行。

添加此以查看您的进度（尽管需要更长的时间）：

for(i=2;i<num;i++)
    {
        if(num%i==0)
        {
            flag=0;
            printf("%d,", num); /* <== show the prime */
            break;
        }
    }

编辑

正如其他人指出的那样，这是计算素数的最慢方法。也许您的任务的目的是让您查找（并实施）更快的任务？

于 2010-10-04T02:42:40.863 回答
0

您的程序导致整数溢出，您可以使用 long long 来修复它。

此外，您检查数字是否为素数的算法也不是很好。另一种同样简单的方法是测试数字 2 的平方根。您只需检查数字的平方根即可确定它是否为素数。

于 2010-10-04T02:58:11.493 回答
0

一个简单的改变会告诉你你的程序运行得有多快，以及它需要做多少工作。每 100 次迭代就可以轻松打印出您的状态。（或者您可以将其设置为 1000 或 10000 次迭代。）

认识到您可以将循环速度加倍IsPrime。
勾选 2 后，只需要勾选奇数，可以用i+=2代替推进i++。

如果您关心速度，为什么要花这么多时间检查偶数？（请注意，一旦开始只做奇数，您还需要将输出测试更改为奇数）

您也可以通过避免那里的偶数来使循环速度加倍。main（同样，你必须对特殊情况 2，然后使用 i+=2，从 3 开始得到 3、5、7、9....）

通过使运行中的循环IsPrime速度提高两倍，并使main运行中的循环速度提高两倍，这应该使您的程序运行速度提高4 倍。（如果之前需要一个小时，现在需要 15 分钟。）

您可以进行的另一项重大速度改进只是将循环运行到sqrt(num)，而不是num

因为我讨厌引入浮点函数，例如sqrt，所以我建议使用一个接近的近似值，它会在通过 sqrt 边界的 100 次迭代内停止，并且还会定期显示状态更新。

if (num%2 == 0)
{
    flag=0;
    return flag;
}

/* Now that we checked 2, we only need to check odd numbers from now on. */
for(i=3;i<num;i+=2)
{
    if (i%101 == 0)
    {
        printf("i is %d out of %d\n", i, num);
        if (i*i > num)
        {
            break;  /* If you pass the sqrt boundary, quit. */
        }
    }

    if(num%i==0)
    {
        flag=0;
        break;
    }
}

PS我把这段代码放到了一个 C# 项目中（小移植）。诚然，它现在运行在 64 位操作系统上，具有更好的编译器和 2.8GHz CPU。
它运行了不到 20 秒。

于 2010-10-04T03:02:30.893 回答