素数判断c语言
什么是素数？
素数又叫质数，指在大于1的自然数中，除了1和本身，不能被其他自然数整除的数。例如：2、3、5、7、11、13、17、19等都是素数。
素数判断的方法
对于一个数n，如果想要判断它是否为素数，常见的方法有以下几种：
1.暴力枚举法
c++判断素数只需要从2到n-1枚举每一个数，如果n能被其中的一个数整除则说明n不是素数。这种方法的时间复杂度为O(n)。
2.枚举到根号n
因为n如果有一个大于根号n的因子，必然有一个小于根号n的因子，所以只需要枚举到根号n即可。
3.筛法
筛法是一种更加高效的素数判断方法，它可以在O(nloglogn)的时间内得到小于等于n的所有素数。
具体流程：
1）先将2到n的数列打上标记，都为素数；
2）从2开始，将素数的倍数打上合数的标记，比如4、6、8、10…都为合数，清除2的所有倍数
3）下一个未被打上标记的数是素数
4）重复第二步，直到整个数列都被处理过
代码实现
下面是一段C语言代码，用于判断一个数是否为素数：
#include <stdio.h>
int isPrime(int n){
  int i;
  if(n<2) return 0; //小于2不是素数
  for(i=2;i*i<=n;i++) //i的平方大于n就没必要再执行下去了，提高效率
  {
    if(n%i==0) return 0;
  }
  return 1;
}
int main(){
  int n;
  scanf("%d",&n);
  if(isPrime(n)) printf("%d是素数\n",n);
  else printf("%d不是素数\n",n);
  return 0;
}
可以看到，代码非常简单易懂， 只要判断n是否小于2，然后从2开始枚举每个数，看能否被n整除即可。
代码优化
上面的代码虽然可以判断素数，但是效率并不高，当n很大时，运行速度会非常慢。下面，我们来优化代码：
1)只需要循环到sqrt（n）即可。因为如果存在一个数大于sqrt（n）能整除n，那么一定有个数小于sqrt（n）能够整除n。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。