21xrx.com
2025-03-21 16:04:54 Friday
文章检索 我的文章 写文章
C语言实现素数判断
2023-06-18 10:09:10 深夜i     17     0
素数 质数 C语言 试除法 暴力枚举

素数，也叫质数，指的是除了1和它本身以外没有其他因数的自然数。素数在数学和计算机科学领域有着重要的应用，因此判断一个数是否为素数是一个非常基础的问题，也是程序员们的必修课之一。

在C语言中，实现素数判断的方法有很多种，其中比较常见的方法有两种：暴力枚举和试除法。暴力枚举方法需要遍历1至n-1之间的所有自然数，看是否都不存在n的因子；而试除法则只需要试除n的所有小于等于sqrt(n)的因子即可。

以下是使用试除法实现素数判断的C语言代码：

#include 
#include 
int is_prime(int n) {
  if(n < 2)
    return 0;
  
  int i;
  for(i = 2; i <= sqrt(n); i++) {
    if(n % i == 0)
      return 0;
    
  }
  return 1;
}
int main() {
  int n;
  printf("请输入一个自然数：");
  scanf("%d", &n);
  if(is_prime(n)) {
    printf("%d是素数", n);
  } else {
    printf("%d不是素数", n);
  }
  return 0;
}

在代码中，我们使用了sqrt()函数来求n的平方根，因为试除法只需要试除小于等于sqrt(n)的因子。

通过对源码的分析，我们可以得到该程序的几个

  
  

评论区