c - 循环运行所花费的时间

Question

我是编程新手。我正在尝试一个程序来打印第 n 个质数。代码如下:

##program to print the nth prime number
nreq=input("Enter a number ")  
pctr=0 ##counter of the prime numbers
num=2

while pctr!=nreq:
    ctr=0 ##counter
    i=2
    while i<=num:
        if num%i==0:
            ctr=ctr+1
        i=i+1
    if ctr==1:
        pctr=pctr+1
    if pctr==nreq:
        break
    num=num+1


print 'the {}th prime number is {}'.format(nreq,num)  

我在 python 和 C 中尝试了相同的算法。对于更大的数字，与 C 相比，python 中输出所花费的时间要长得多。为什么会发生这种情况？有人可以解释一下两者执行的区别吗？

我的 C 代码如下:

#include<stdio.h>


void main()
{

int num=2,nreq,ctr=0,pctr=0,i;

printf("enter the number of prime required");
scanf("%d",&nreq);

    while(pctr!=nreq)
{

    ctr=0;
    for(i=2;i<=num;i++)
        if(num%i==0)
            ctr++;

    if(ctr==1)
        pctr++;

    if(pctr==nreq) 
        break;
    num++;
}

printf("the %dth prime number is %d",nreq,num);
}

Answer 1

C is often faster than Python因为它是编译的，而且不那么抽象。这意味着 C 生成机器代码，然后由计算机执行。另一方面，Python 的解释器实际上是一个 C 程序，它在运行时遍历语法树并执行它，在许多情况下速度较慢。如果你想让你的 Python 代码运行得更快，那么你可以尝试另一个 Python implementation .

也就是说，您的算法效率很低，O(n^2)(尽管我不确定是否有更简单的算法来解决这个问题)。换句话说，随着输入变大，最坏情况下的复杂性扩展得更快。有关复杂性的更多信息，请参阅 here .

编辑:感谢@laindir 提供了如何使这段代码不那么复杂的解释:

An easy optimization is to store the primes so far discovered, so that only they are checked in the inner loop. That brings it down from O(n^2) to O(n * p) where p is the number of primes less than n. The next simplest is doing something in the outer loop to skip over numbers guaranteed not to be prime--a technique known as sieving--e.g., skipping even numbers. A very simple sieve is Eratosthenes--that's the one used by the unix utility primes.