21xrx.com
2024-11-05 16:38:29 Tuesday
登录
文章检索 我的文章 写文章
C语言实现素数判断
2023-06-18 10:09:10 深夜i     --     --
素数 质数 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)的因子。

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

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复