无法理解代码背后的逻辑，这是一个在两个给定数之间产生质数的优化问题。

Question

彼得想为他的密码系统生成一些质数。请帮助他 你的任务是在两个给定的数字之间生成所有的质数。

输入输入以单行中的测试案例数t开始(t<=10)。在接下来的t行中，每一行都有两个数字m和n(1 <=m <=n <=1000000000, n-m<=100000)，用空格隔开。

输出对于每一个测试案例，打印所有素数p，使m <=p <=n，每行一个数字，测试案例用空行隔开。

例子输入：m <=p <=n，一个数字行，测试案例用空行隔开。

2
1 10
3 5

输出：

2
3
5
7

3
5

警告：大的输入输出数据，对某些语言要小心(虽然如果算法设计得好，大多数应该没问题)

我在google上查了一下，找到了上述问题的优化方案，这是代码。

#include <iostream>
#include <cmath>
#include <vector>
#include <set>
using namespace std;

int main() {
    vector<int> primes;
    primes.push_back(2);

    for (int i = 3; i <= 32000; i+=2) {
        bool isprime = true;
        int cap = sqrt(i) + 1;

        vector<int>::iterator p;
        for (p = primes.begin(); p != primes.end(); p++) {
            if (*p >= cap) break;
            if (i % *p == 0) {
                isprime = false;
                break;
            }
        }
        if (isprime) primes.push_back(i);
    }

    int T,N,M;

    cin >> T;

    for (int t = 0; t < T; t++) {
        if (t) cout << endl;

        cin >> M >> N;
        if (M < 2) M = 2;

        int cap = sqrt(N) + 1;

        set<int> notprime;
        notprime.clear();

        vector<int>::iterator p;
        for (p = primes.begin(); p != primes.end(); p++) {

            if (*p >= cap) break;
            int start;

            if (*p >= M) start = (*p)*2;
            else start = M + ((*p - M % *p) % *p); //not able to understand this logic.

            for (int j = start; j <= N; j += *p) {
                notprime.insert(j);
            }
        }

        for (int i = M; i <= N; i++) {
            if (notprime.count(i) == 0) {
                cout << i << endl;
            }
        }

    }
    return 0;
}

我无法理解上面的代码。请大家帮我理解一下。我就是不明白这个程序背后的逻辑（我知道STL，只是想了解一下逻辑）。

Answer 1

它真的很简单。你预先计算所有存在于你的范围内的质数。然后对于每个质数的倍数，除了第一个，你标记为 "非质数"。

你标记的行只是计算特定质数的倍数在M到N范围内的第一次出现。

编辑：更多解释。

这个方法通过首先搜索所有非质数来找到质数。剩下的就是质数.

要做到这一点，第一步它计算所有 "小 "质数。然后，对于每个小质数，它标记了所有符合目标范围的倍数。要做到这一点，你需要首先计算这个质数在你的范围内的首次出现 - 这就是 "start "变量。基本上，它是质数的第一个倍数，>= M.当你有了 "start"，你只需将质数加到当前的数字上，就可以标记所有的倍数，直到你达到N。

如果你仍然对 "start "是如何计算的感到困惑，试着想想如何找到 "x"，使它成为 "x = A * y "和 "x >= M"，在这里你知道A和M，但不知道 "y"。

另外我觉得这个算法可能有错误。因为它应该对 "nonprime "集合中的每个值完成这个循环。但是，如果第一个未计算的质数总是>N，可能就无所谓了。