时间戳

首页 > 解决方案 > 仅使用奇数除数计算素数较慢

c - 仅使用奇数除数计算素数较慢

问题描述

我编写了一个小的 C 程序来计算素数，现在尝试尽可能优化代码。

在程序的第一个版本中，我正在检查一个数字是否为偶数（模 2），如果是，我将继续下一个数字。

在我的第二次修订中，我尝试通过将要检查的数字增加 2 来仅检查奇数是否可能是素数（所以我将从 3 开始，然后检查 5，然后检查 7，然后检查 9，然后检查 11 等）。

我认为这会更快，因为我已经用我的代码对模 2 进行了额外的检查，并简单地将其替换为加法。然而，令我惊讶的是，仅检查奇数的代码在大多数情况下运行速度稍慢于检查所有数字的实现。

这是代码（它包含我在评论中的修订之间所做的更改，无论它说//CHANGE）

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

unsigned long i = 3; //CHANGE No 1 - it was i = 2;

bool hasDivisor(unsigned long number)
{
    //https://stackoverflow.com/questions/5811151/why-do-we-check-up-to-the-square-root-of-a-prime-number-to-determine-if-it-is-pr
    unsigned long squareRoot = floor(sqrt(number));

    //we don't check for even divisors - we want to check only odd divisors
    //CHANGE No 2 - it was (number%2 ==0)
    if(!((squareRoot&1)==0)) //thought this would boost the speed
    {  
        squareRoot += 1;
    }

    for(unsigned long j=3; j <= squareRoot; j+=2)
    {
        //printf("checking number %ld with %ld \n", number, j);
        if(number%j==0)
        {
            return true;
        }
    }
    return false;
}

int main(int argc, char** argv)
{
    printf("Number 2 is a prime!\n");
    printf("Number 3 is a prime!\n");

    while(true)
    {
        //even numbers can't be primes as they are a multiple of 2
        //so we start with 3 which is odd and contiously add 2
        //that we always check an odd number for primality
        i++; //thought this would boost the speed instead of i +=2;
        i++; //CHANGE No 3 - it was a simple i++ so eg 3 would become 4 and we needed an extra if(i%2==0) here

        //search all odd numbers between 3 and the (odd ceiling) sqrt of our number
        //if there is perfect division somewhere it's not a prime
        if(hasDivisor(i))
        {
            continue;
        }        
        printf("Number %ld is a prime!\n", i);
    }
    return 0;
}

我正在使用带有 GCC 8.2.1 版的 Arch Linux x64 并编译：

gcc main.c -lm -O3 -o primesearcher

虽然我也用 O1 和 O2 进行了测试。

我正在使用以下命令进行“基准测试”：

./primesearcher & sleep 10; kill $!

它运行程序 10 秒，并在这段时间内向终端输出素数，然后将其杀死。我显然尝试让程序运行更多（30、60 和 180 秒），但结果大约有 9/10 的时间有利于版本检查偶数（模 2 版本在被杀死之前发现了更大的素数） .

知道为什么会这样吗？也许最终在代码方面有问题？

标签： coptimizationprimesmathematical-optimization

解决方案

代码if(!((squareRoot&1)==0))比没有测试要慢，因为它很少有好处。

请记住，对于大多数人number来说，由于number%j测试提前返回，迭代限制永远不会达到。随着成长，素数往往变得稀有number。

一次罕见的额外迭代不会被测试的重复成本所抵消。

比较!((squareRoot&1)==0)是number%2 ==0没有意义的。

当差异很小时，OP 的测试速度方法很容易出错：“大多数时候运行速度有点慢”显示了不一致。

大量的时间在printf(). 为了比较主要的计算性能，需要消除 I/O。

kill也不是那么精确。

相反，形成一个循环以在达到 4,000,000,000 之类的值时停止i并计时。

代码还有其他弱点：

unsigned long squareRoot = floor(sqrt(number));number由于转换number为例程时的舍入double和不精确，可能会为大创建错误的根。sqrt()OP 的参考解决了数学算法的需求。然而，考虑到实际计算的局限性，这种 C 代码实现很容易失败。

相反，建议

// Prime test for all unsigned long number
bool isPrime(unsigned long number) {
  if (number % 2 == 0) {  // This can be eliminated if `number` is always odd.
    return number == 2;
  }

  for (unsigned long j = 3; j <= number/j; j += 2) {
    if (number%j == 0) {
      return false;
    }
  }

  return number > 2;
}

现代编译器的成本number/j通常为零，因为他们看到number%j并一次有效地计算商和余数。因此j <= squareRoot实现了 1) 的限制，无需进行昂贵的sqrt()计算 2)number与sqrt()使用不同，对于大的 是准确的。

使用匹配的说明符。 u，不适d用于无符号类型。

// printf("Number %ld is a prime!\n", i);
printf("Number %lu is a prime!\n", i);

在这里使用全局i是一种弱编码风格。建议重新编码并通过函数传递。

要获得更多实质性改进，请查看埃拉托色尼筛法并保留以前发现的素数列表并测试这些素数，而不是所有奇数。

Prime 测试是一个包含许多更高级想法的深度主题。

推荐阅读