尽管遍历了一半的迭代次数，但循环速度并不快？

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

就是这条线：

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

一旦n=true;执行，由于b条件，&& n==0循环退出。第一次测试就会发生这种情况：每个偶数都可被2整除，即a[0]。因此，对于偶数（如果使用p++而不是p=p+2，则包含），内循环非常快，比典型的奇数快得多。这解释了为什么包含它们会产生如此小的差别

Answer 2

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

如果你没有看到你的内部循环完成两次，那么当a[b/2]为1时，考虑b是相同的，就像b为0时那样。