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

Question

我们有一个与prime有关的编码作业，我的 friend 写了这段代码。它很长，我不太了解它，并且我觉得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，sieve[21]=3等。

这是Eratosthène筛子的基础，Erastothène筛子是一种非常古老的算法(用于寻找素数)(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;

与:

while(1) {
...
}

因此，真正的问题是，为什么那里还有其他“无限”循环？

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

我可以优化这个吗？

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

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

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