c - 我如何执行 "Millions of Calculations?"

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 ，这可以更有效地确定特定范围内的所有素数。