为什么使用所有数字测试质数要比仅使用质数更快

Question

我制作了此程序来生成质数。我知道有很多公式可以使它们生成速度快100倍，但这就是我所做的。

1：我尝试将i除以i下的所有数字。那是最简单的方法，但是我虽然效率不高，因为除以2后，您不需要除以4，依此类推。

2：我列出了一个小于i的质数，然后用该数除以i。我使用std :: iterator浏览了该列表，因为我看到它已在所有stackoverflow答案和其他教程中使用。事实证明它要慢得多。就像用了22秒而不是2秒。

3：我尝试使用int来遍历列表，然后又花了2秒钟。

[接下来，我用1 000 000来查看方法1和3之间的差异。令我惊讶的是，方法1更快。这是为什么？难道不应该只使用质数来测试就比使用所有数字更快吗？

#include <iostream>
#include <vector>
#include <chrono>

int main()
{
    std::cout << "how high do you want to generate prime numbers? ";
    int x;
    // typed 1 000 000
    std::cin >> x;
    auto starttime = std::chrono::high_resolution_clock::now();
    std::vector<unsigned int> primes;
    bool isPrime;
    for (int i = 2; i <= x; ++i) {
        isPrime = true;

        // takes 293 seconds
        //for (int div{ 2 }; div < i; ++div) {
            //  if ((i % div) == 0) {

        // takes really really long
        //for (std::vector<unsigned int>::iterator div = primes.begin(); div != primes.end(); ++div) {
            //if ((i % *div) == 0) {

        // takes 356 seconds
        for (int iter = 0; iter < primes.size(); ++iter) {
            if ((i % primes[iter]) == 0) {

                isPrime = false;
                break;
            }
        }
        if (isPrime) {
            primes.push_back(i);
            std::cout << i << " ";
        }
    }
    std::cout << "generating prime numbers up to " << x << " took " <<
        round(static_cast<std::chrono::duration<double>>((std::chrono::high_resolution_clock::now() - starttime)).count())
        << " seconds.";
}

Answer 1

由于第三种用法而使用vector<unsinged int>。尤其是primes.push_back会导致分配。最初尝试primes.reserve