我应该保留这个函数来寻找第 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，sieve[21]=3，等等

这是 Eratosthè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) {
...
}

所以 真正的 问题是为什么那里有一些 "infinite" 循环？

这是因为您正在寻找第 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 的素数整除（可能通过在数组中存储稍微不同的值） .

我应该保留这个函数来寻找第 n 个素数还是可以优化它？

Should I keep this function for finding nth prime or can this be optimized?

c++

algorithm

math

primes