尽管循环次数减半，但循环速度并不快？

Question

我写了一个搜索素数的程序：

#include <iostream>
#include <fstream>
#include <chrono>

typedef std::chrono::high_resolution_clock Clock;
using namespace std;

int main() {
    int p;
    int x = 1;
    int b;
    int a[1000000];
    bool n = false;
    a[0] = 2;
    a[1] = 3;

    auto t1 = Clock::now();

    ofstream outfile;
    outfile.open("p.txt");

    for (p = 3; p < 7500000; p = p + 2)
    {
        for (b = 0; b <= x && n == 0; b++)
        {
            if (p % a[b / 2] == 0)
            {
                n = true;
            }
        }
        if (n == false)
        {
            cout << p << endl;
            outfile << p << endl;
            x++;
            a[x] = p;
        }
        else
        {
            n = false;
        }
    }

    auto t2 = Clock::now();
    std::cout
        << std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count()
        << " nanoseconds" << std::endl;
    outfile.close();
}

最初对于循环增量我有 p++，但我将其更改为 p=p+2 因为所有素数本质上都是奇数，不需要检查偶数。问题是当我对此进行基准测试时，新旧代码之间的速度没有差异。那么这个过程中的瓶颈是什么，如果检查所有数字与检查一半没有区别？有没有更好的方法来解决这个问题？

Answer 1

你的外循环跳过了一半的数字。但是你的内部循环测试每个数字两次。所以你放弃了所有的收获。

如果您没有看到您的内部循环将所有操作都执行两次，请考虑当 b 为 1 时 a[b/2] 与 b 为 0 时相同。

Answer 2

就是这一行：

for(b=0; b<=x && n==0; b++)

一旦 n=true; 执行，b 循环会因为 && n==0 条件而退出。这发生在第一个测试中：每个偶数都可以被二整除，即 a[0]。因此，对于偶数（如果使用 p++ 而不是 p=p+2，则包括偶数），内部循环非常快，比典型的奇数快得多。这解释了为什么将它们包括在内几乎没有什么区别。

尽管循环次数减半，但循环速度并不快？

Loop not faster despite looping through half as many iterations?

c++

primes

loops