超长冗余代码高效吗？

Question

我正在尝试使用希腊人筛算法找到一些素数。我有一些效率问题。这是代码：

void check_if_prime(unsigned number)
{
    unsigned index = 0;
    while (primes[index] <= std::sqrt(number))
    {
        if (number % primes[index] == 0) return;
        ++index;
    }
    primes.push_back(number);
}

而且，因为我编码了巨大的 2/3/5/7/11/13 原轮，代码是 5795 行长。

for (unsigned i = 0; i < selection; ++i)
{
    unsigned multiple = i * 30030;
    if (i!=0) check_if_prime( multiple+1 );
    check_if_prime ( multiple+17 );
    check_if_prime ( multiple+19 );
    check_if_prime ( multiple+23 );
    // ...so on until 30029
}

优化标志：-O3、-fexpensive-optimizations、-march=pentium2

20 分钟内有 2500 万个质数，CPU 停留在 50%（不知道为什么，尝试了实时优先级但变化不大）。输出文本文件的大小为 256MB（稍后将更改为二进制文件）。

编译需要很长时间！可以吗？如何在不影响效率的情况下使其更快？
for循环开头的if语句可以吗？我读过 if 语句花费的时间最长。
还有关于代码而不是算法的其他信息吗？有什么可以让它更快的吗？哪些语句比其他语句更快？
甚至更大的轮子（高达 510510，不只是 30030，该死的很多行）是否会在一天内编译？

我想找到 2^32 以内的所有素数，稍作优化就可以节省一些时间和电力。提前致谢！

编辑： 不是求算法，求代码改进，如果有的话！

Answer 1

关于您的程序的性能，我可以这样说：

您的主要问题可能是对 std::sqrt() 的调用。这是一个浮点函数，专为获得完全精确的结果而设计，它肯定需要相当多的周期。我敢打赌，如果您改用此检查，您会快得多：
```
while (primes[index]*primes[index] < number)
```
这样你使用的是整数乘法，这对于现代 CPUs 来说是微不足道的。
for() 循环开头的 if 语句与性能无关。它执行的次数还不够多。您的内部循环是 check_if_prime() 内的 while 循环。那就是你需要优化的那个。
我看不出你是怎么做输出的。有一些输出方式会严重拖慢你的速度，但我认为这不是主要问题（如果它真的是个问题的话）。

代码大小可能是个问题：您的 CPU 指令缓存容量有限。如果您的 6k 行不适合一级指令缓存，那么惩罚可能会很严重。如果我是你，我会使用数据而不是代码重新实现轮子，我。即：

unsigned const wheel[] = {1, 17, 19, 23, ...};    //add all your 6k primes here
for (unsigned i = 0; i < selection; ++i)
{
    unsigned multiple = i * 30030;
    for(unsigned j = 0; j < sizeof(wheel)/sizeof(*wheel); j++) {
        check_if_prime(multiple + wheel[j]);
    }
}

Answer 2

在调试器下获取它运行，然后逐条指令单步执行它，并在每一点上理解它在做什么以及为什么。

这让你站在 CPU 的立场上，你会看到疯狂的程序员让你做的所有愚蠢的事情，你会看到你可以做得更好。

这是使您的代码尽可能快地运行的一种方法。

程序大小本身只会影响速度，如果你的速度太快以至于缓存成为问题。

Answer 3

以下是一些检查数字是否为质数的技巧：

bool is_prime(unsigned int number) // negative numbers are not prime.
{
  // A data store for primes already calculated.
  static std::set<unsigned int> calculated_primes;

  // Simple checks first:
  // Primes must be >= 2.
  // Primes greater than 2 are odd.
  if (   (number < 2)
      || ((number > 2) && ((number & 1) == 0) )
  {
    return false;
  }

  // Initialize the set with a few prime numbers, if necessary.
  if (calculated_primes.empty())
  {
     static const unsigned int primes[] =
     { 2, 3, 5, 7, 13, 17, 19, 23, 29};
     static const unsigned int known_primes_quantity =
         sizeof(primes) / sizeof(primes[0]);
     calculated_primes.insert(&primes[0], &primes[known_primes_quantity]);
  }
  // Check if the number is a prime that is already calculated:
  if (calculated_primes.find(number) != calculated_primes.end())
  {
    return true;
  }

  // Find the smallest prime to the number:
  std::set<unsigned int>::iterator prime_iter =
      calculated_primes.lower_bound(number);
  // Use this value as the start for the sieve.
  unsigned int prime_candidate = *prime_iter;
  const unsigned int iteration_limit = number * number;
  while (prime_candidate < iteration_limit)
  {
     prime_candidate += 2;
     bool is_prime = true;
     for (prime_iter = calculated_primes.begin();
          prime_iter != calculated_primes.end();
          ++prime_iter)
     {
       if ((prime_candidate % (*prime_iter)) == 0)
       {
         is_prime = false;
         break;
       }
     }
     if (is_prime)
     {
       calculated_primes.insert(prime_candidate);
       if (prime_candidate == number)
       {
         return true;
       }
     }
  }
  return false;
}

注意：这是未经测试的代码，但演示了一些检查数字是否为质数的技术。

超长冗余代码高效吗？

Is super long redundant code efficient?

c++

algorithm

optimization

performance

sieve-of-eratosthenes