C - 确定数字是否为素数

Question

我试图想出一个方法,它接受一个整数并返回一个布尔值来说明数字是否为素数,我不知道多少C; 有人会关心给我一些指示吗？

基本上,我会在C#中这样做:

static bool IsPrime(int number)
{
    for (int i = 2; i < number; i++)
    {
        if (number % i == 0 && i != number)
            return false;
    }
    return true;
}

Answer 1

好吧,所以忘了C.假设我给你一个号码,并要求你确定它是否是素数.你怎么做呢？清楚地写下步骤,然后担心将它们转换为代码.

一旦确定了算法,就可以更容易地找出如何编写程序,以及让其他人帮助您编写程序.

编辑:这是您发布的C#代码:

static bool IsPrime(int number) {
    for (int i = 2; i < number; i++) {
        if (number % i == 0 && i != number) return false;
    }
    return true;
}

这几乎是有效的C; boolC中没有类型,没有true或者false,所以你需要稍微修改一下(编辑:Kristopher Johnson正确地指出C99添加了stdbool.h标题).由于有些人无法访问C99环境(但你应该使用一个!),让我们做一个非常小的改变:

int IsPrime(int number) {
    int i;
    for (i=2; i<number; i++) {
        if (number % i == 0 && i != number) return 0;
    }
    return 1;
}

这是一个完全有效的C程序,可以满足您的需求.我们可以毫不费力地改进它.首先,注意i总是小于number,所以i != number总是成功的检查; 我们可以摆脱它.

而且,你实际上并不需要一直尝试除数number - 1; 当你达到sqrt(数字)时你可以停止检查.由于sqrt是一个浮点运算,并带来了一大堆微妙之处,我们实际上不会计算sqrt(number).相反,我们可以检查i*i <= number:

int IsPrime(int number) {
    int i;
    for (i=2; i*i<=number; i++) {
        if (number % i == 0) return 0;
    }
    return 1;
}

但最后一件事是; 原始算法中有一个小错误!如果number是负数,或零或一,则此函数将声明该数字为素数.您可能希望正确处理,并且您可能希望number保持未签名,因为您更可能只关心正值:

int IsPrime(unsigned int number) {
    if (number <= 1) return 0; // zero and one are not prime
    unsigned int i;
    for (i=2; i*i<=number; i++) {
        if (number % i == 0) return 0;
    }
    return 1;
}

这肯定不是检查一个数字是否为素数的最快方法,但它确实有效,而且非常简单.我们几乎不需要修改你的代码!

Answer 2

我很惊讶没有人提到这一点.

使用Eratosthenes的Sieve

细节:

1. 除了1和他们自己之外,基本上非主要数字可以被另一个数字整除
2. 因此:非主要数字将是素数的乘积.

Eratosthenes的筛子找到一个素数并存储它.当检查新数字的素数时,将根据已知的素数列表检查所有先前的素数.

原因:

1. 这个算法/​​问题被称为" 令人尴尬的并行 "
2. 它创建了一个素数集合
3. 它是动态编程问题的一个例子
4. 它快!

Answer 3

斯蒂芬佳能回答得非常好!

但

• 通过观察所有质数的形式为6k±1,除了2和3之外,可以进一步改进算法.
• 这是因为对于某些整数k和i = -1,0,1,2,3或4,所有整数可以表示为(6k + i); 2除(6k + 0),(6k + 2),(6k + 4); 和3分(6k + 3).
• 因此,更有效的方法是测试n是否可被2或3整除,然后检查所有形式的数字6k±1≤√n.

• 这是测试所有m到√n的3倍.

  int IsPrime(unsigned int number) {
      if (number <= 3 && number > 1) 
          return 1;            // as 2 and 3 are prime
      else if (number%2==0 || number%3==0) 
          return 0;     // check if number is divisible by 2 or 3
      else {
          unsigned int i;
          for (i=5; i*i<=number; i+=6) {
              if (number % i == 0 || number%(i + 2) == 0) 
                  return 0;
          }
          return 1; 
      }
  }
  

Answer 4

1. 构建一个小素数表,并检查它们是否除以输入数.
2. 如果数字存活到1,请尝试增加基础的伪素性测试.例如,参见Miller-Rabin素性测试.
3. 如果你的数字存活到2,你可以得出结论,如果它低于一些众所周知的边界.否则你的答案只会是"可能是素数".您将在Wiki页面中找到这些边界的一些值.