21xrx.com
2025-03-23 09:36:49 Sunday
文章检索 我的文章 写文章
C语言判断素数的方法及代码实现
2023-06-15 17:48:29 深夜i     30     0
C语言 素数 判断 代码实现 暴力枚举 优化枚举 埃拉托色尼筛法

素数，又称质数，是指在大于1的自然数中，除了1和本身之外无法被其他数整除的数。判断一个数是否为素数在数学领域中比较重要，本文将介绍使用C语言判断一个数是否为素数的方法及代码实现。

方法一：暴力枚举

暴力枚举是指对于一个数n，从2开始依次枚举到n-1，判断是否能整除n。如果能整除，那么n就不是素数，反之则是素数。这种方法的时间复杂度为O(n)。

方法二：优化枚举

优化枚举是指对于一个数n，在从2开始枚举到根号n的过程中，如果发现n能被某个数整除，则n必然能被另外一个小于根号n的数整除，因此可以直接判断n不是素数。这种方法的时间复杂度为O(√n)。

方法三：埃拉托色尼筛法

埃拉托色尼筛法是一种筛选素数的方法，其基本原理是先构造一个从2开始的自然数序列，然后从2开始不断筛选掉所有的倍数，最后剩下的就是素数。这种方法的时间复杂度为O(n log log n)。

下面是使用C语言实现判断素数的代码：

#include 
int is_prime(int n)
{
  int i;
  if(n <= 1)
    return 0;  //负数、0、1都不是素数
  for(i = 2; i <= n/2; i++)
    if(n % i == 0) //能整除
      return 0;
  return 1;
}
int main()
{
  int n, flag;
  printf("请输入一个正整数：");
  scanf("%d", &n);
  flag = is_prime(n);
  if(flag)
    printf("%d是素数", n);
  else
    printf("%d不是素数", n);
  return 0;
}
  
  

评论区