21xrx.com
2024-12-27 20:46:45 Friday
登录
文章检索 我的文章 写文章
C语言中最快的素数判断方法
2023-06-14 11:30:19 深夜i     --     --
C语言 素数 判断方法

在程序设计中,常常需要判断一个数是否为素数。素数是指只能被1和本身整除的自然数。虽然有多种判断素数的方法,但是在C语言中,有一种被认为是最快的方法。

该方法是通过判断一个数是否能被从2到该数的平方根之间的所有自然数整除。如果都不能整除,则该数是素数。

下面是该方法的C语言代码实现:

int is_prime(int num){

  int i=2;

  int sqr=(int)sqrt(num);

  while(i<=sqr){

    if(num%i==0)不是素数

    i++;

  }

  return 1;      //能整除,是素数

}

该方法的时间复杂度为O(sqrt(n)),比传统的试除法要快很多。

如果要判断多个数是否为素数,可以在循环中反复调用上述函数。也可以用线性筛法或欧拉筛法来预处理出一定范围内的素数,再根据这些素数来判断其他数是否为素数。

  
  

评论区

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