C语言中的素数判断方法及实现 |21xrx.com

C语言中的素数判断方法及实现

2023-06-16 16:09:27 深夜i -- --

C语言素数暴力法试除法优化方法时间复杂度

素数是指只能被1和自己整除的正整数，是数学中非常基础但又十分重要的概念。在C语言中，判断一个数是否是素数有多种方法，下面将介绍其中比较常用的两种方法。

一、暴力法

暴力法是最简单粗暴的方法，只需要依次判断该数能否被比它小的正整数整除即可。具体实现如下：


#include
int is_prime(int n)
{
  int i;
  if(n<=1)
    return 0;
  for(i=2;i
  {
    if(n%i==0)
      return 0;
  }
  return 1;
}
int main()
{
  int n;
  scanf("%d",&n); //输入要判断的数
  if(is_prime(n))
    printf("%d是素数\n",n);
  else
    printf("%d不是素数\n",n);
  return 0;
}

由于暴力法需要依次判断到该数的平方根，因此时间复杂度为O(sqrt(n))。

二、优化法

试除法是一种比较常用的优化方法，它的思路是只需要判断该数是否能被2到它的平方根中的素数整除即可。具体实现如下：


#include
#include
int is_prime(int n)
{
  int i;
  if(n<=1)
    return 0;
  if(n==2)
    return 1;
  if(n%2==0) //如果n是偶数，直接返回0
    return 0;
  for(i=3;i<=sqrt(n);i+=2) //只需要判断奇数
  {
    if(n%i==0)
      return 0;
  }
  return 1;
}
int main()
{
  int n;
  scanf("%d",&n); //输入要判断的数
  if(is_prime(n))
    printf("%d是素数\n",n);
  else
    printf("%d不是素数\n",n);
  return 0;
}

与暴力法相比，优化法可以大大减少无用的判断次数，因此时间复杂度更低，为O(sqrt(n)/2)。

上一篇: idea打包java可执行jar包

下一篇: 如何使用Java获取系统中所有的方法数量

评论区

()

相似文章