如何执行“数百万次计算？”

Question

我的代码粘贴在下面。当我运行这个程序时，它一直在计算。我使用的是旧的 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;
}

Answer 1

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

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

为此，您确实需要使用类似以下内容的内容： http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes< /a>，它可以更有效地确定特定范围内的所有素数。

Answer 2

这样的程序需要多长时间才能执行？

这完全取决于您的平台。我怀疑，由于您正在执行〜（两百万）^ 2 次操作（〜四万亿）计算，所以时间太长了。

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

Answer 3

正如其他人所说，这需要很长时间。另一种有趣的方法是埃拉托斯特尼筛法。您可以在以下位置阅读相关内容：

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

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

Answer 4

另类答案

gotoxy(25,25);

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

Answer 5

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

如果TurboC++具有，则这些实现限制在该标头中定义了相应的宏

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

如果这失败了您需要自己“计算”限制。我正在切换到无符号，因为它们没有溢出问题，我只需要“计算”上限（下限为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 goes from -2147483648 to 2147483647.
long goes from -9223372036854775808 to 9223372036854775807.

和第二个 程序输出程序输出

unsigned ints go all the way to 4294967295
unsigned longs go all the way to 18446744073709551615

Answer 6

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

#define TWO_MILLION 2*1000*1000

这很糟糕。当您稍后更改该值时，您要么会出现 name-content-mismatch:

#define TWO_MILLION 5*1000*1000

，要么将其重命名为

#define FIVE_MILLION 5*1000*1000

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

Answer 7

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

所以在计算出筛数之后，你只需要测试被该行的数字整除与筛子一起，并且小于n的平方根。

Answer 8

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

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

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

编辑

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

Answer 9

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

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

Answer 10

一个简单的更改将显示您的程序运行的速度以及它需要完成多少工作。每 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 秒。