我应该保留此函数来查找第n个素数还是可以对其进行优化？

Question

我们有一个与prime有关的编码作业，我的朋友写了这段代码。它很长，我不太了解它，并且有goto，我认为这很皱眉，所以我不知道。能帮助我们决定是否应该保留它吗？

int getNth (int nth){
    vector<int> prime;
    int sievelmt = nth*10;
    int i,j;
    func:
    vector<int> sieve(sievelmt, -1);
    prime.push_back(2); if (nth == 1) return 2;
    prime.push_back(3); if (nth == 2) return 3;
    prime.push_back(5); if (nth == 3) return 5;
    for (i = 2; i <= sievelmt; i++)
    {
        if (i%2==0||i%3==0||i%5==0) continue;
        if (sieve[i] == -1)
        {
            prime.push_back(i); if (prime.size()==nth) return prime[prime.size()-1];
            for ( j = 1; i*j <= sievelmt; j++) sieve[i*j]=j;
        }
        else continue;
    }    
    sievelmt *= 10;
    sieve.clear(); prime.clear();
    goto func;
    return -1;
}

Answer 1

算法的核心是这一行：

for ( j = 1; i*j <= sievelmt; j++) sieve[i*j]=j;

对于给定的i，它填充数组sieve的位置，该位置是i的倍数，其倍数为秩。想象i=7，然后想象sieve[7]=1，sieve[14]=2,筛[21] = 3`，依此类推

这是Eratosthène筛子的基础，这是一种非常古老的查找质数的算法。如果使i从2到某个值不等，则这将标记索引不是素数的每个位置。最后，每个未标记的位置都是一个素数。让我们看看：

• i=2 .1.2.3.4.5.6.7.
• [i=3 .112.2.435.4.75，3是素数（第一次访问位置3）
• i=4 .111.2.235.3.75
• [i=5 .11112.232.3.73，5是质数（第一次访问位置5）
• i=6 .11111.232.3.73
• [i=7 .111111232.3.23，7是素数
• i=8 .111111132.3.23
• i=9 .111111112.3.23
• i=10 .111111111.3.23
• [i=11 .11111111113.23，11是素数
• 等

为什么这里有goto？不用担心，goto存在许多危险的用法，但是没有。如果您对那一种感觉不满意，请替换：

func:
...
goto func;

with：

while(1) {
...
}

所以real问题是为什么那里还有一个“无限”循环？

这是因为您正在寻找第n个素数，但是您无法轻易确定要捕获第n个素数的数组必须多长时间...因此该实现会尝试使用更大的大小。算法第一次希望第n个素数的大小为10 * n，如果不够，则将大小乘以10，一次又一次，直到第n个素数为in。

我可以优化它吗？

当然，有一些小技巧。首先，您会看到，如果给定的i被2、3或5整除，那么它就不能是素数。那已经实现了：

if (i%2==0||i%3==0||i%5==0) continue;

然后您可能会说，好吧，如果可以被7或11或13等除（以任何其他质数表示），那是一样的！我不会告诉您更多信息，但是您当然可以对算法进行转换，以确定给定的i是否可以被除i以外的任何质数整除（也许是通过在数组中存储稍微不同的值）。