为什么使用所有数字来测试素数比仅使用素数更快

Question

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

我试图用i下的所有数字除以i。这是最简单的方法，但我认为它效率低下，因为除以 2 后不需要除以 4，依此类推。
我制作了一个小于 i 的素数列表，并将 i 除以该列表的数字。我使用 std::iterator 浏览了这个列表，因为我看到它被用在所有 Whosebug 答案和其他教程中。事实证明它慢了很多。好像用了 22 秒而不是 2 秒。
我试过用int遍历list，又花了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

Answer 2

我想说的主要问题是，最常见的是一个数字可以被 2 整除，因此它不是素数。我想第一种方法对编译器和缓存更友好。但很难确定。另外，尝试删除打印并测试花费的时间。根据使用情况，打印往往会使代码变慢很多。

一种确定所有素数的标准方法（有更有效的方法，但这个方法相当简单）。

创建布尔值向量 A，它将指示数字是否为质数。但在开始时将所有变量设置为 true - 除了 A[0]=A[1]=false.
运行 for loop from i = 2 to x。如果 A[i] 为假则跳过它 - i 不是质数。如果 A[i] 为真，则 i 为素数，并将所有 1<k<x/i 的所有 A[i*k] 设置为假。

这两种方法中的任何一种都应该更有效。

为什么使用所有数字来测试素数比仅使用素数更快

Why is using all numbers to test for a prime number faster than using prime numbers only

c++

primes

loops

vector