如何判断⼀个数是否是质数（C语⾔）-超详细
质数是只能被1或者⾃⾝整除的⾃然数（不包括1），称为质数。
判断是否是质数最直观和简单的⽅法就是从2开始直接除，能除尽（余数为0）就不是质数。则C语⾔实现为：
int isprime(int m)
{
int i;
for(i=2;i<m;i++)
if(m%i==0）
return 0;
else
return 1;
}
该算法的时间复杂度O(n)。
可以改进⼀下，根据如果⼀个数是合数，那么它的最⼩质因数肯定⼩于等于它的平⽅根。⽤反证法可以证明⼀下。假设x是n的最⼩质因数，则存在n/x=p。p>x,x*p=n。如果x不⼩于等于它的平⽅根，则x*x>n,⽽p>x，故x*p>n，假设不成⽴。合数是与质数相对应的⾃然数。⼀个⼤于1的⾃然数如果它不是合数，则它是质数。也就是说如果⼀个数能被它的最⼩质因数整除的话，那它肯定是合数，即不是质数。所以判断⼀个数是否是质数，只需判断它是否能被⼩于它开跟号后的所有数整除，因此，这样做的运算少了很多，降低了时间复杂度。C语⾔实现
int isprime(int m)
{
int i;
for(i=2;i<=sqrt(m);i++)    /*sqrt(int n)这个函数需要引⼊math.h头⽂件*/
if(m%i==0）
return 0;
else
return 1;
}
时间复杂度O(根号n)
上⾯两种⽅法是最常见的。如果要判断⼀个范围内的数是否是质数，则需要多次调⽤isprime()函数，时间复杂度变为增加O(n*m)或O(n*跟号m).这时，可以采⽤另⼀种称为“埃拉托⾊尼(Eratosthenes)筛法”的⽅法。埃拉托⾊尼是古希腊的著名数学家。他采取的⽅法是，在⼀张纸上写上1到100全部整数，然后逐个判断它们是否是素数，出⼀个⾮素数，就把它挖掉，最后剩下的就是素数。具体做法如下：
<1> 先将1挖掉(因为1不是素数)。
<2> ⽤2去除它后⾯的各个数，把能被2整除的数挖掉，即把2的倍数挖掉。
<3> ⽤3去除它后⾯的各数，把3的倍数挖掉。
<4> 分别⽤4、5…各数作为除数去除这些数以后的各数。这个过程⼀直进⾏到在除数后⾯的数已全被挖掉为⽌。
如上算法可表⽰为：
<1> 挖去1;
<2> ⽤刚才被挖去的数的下⼀个数p去除p后⾯各数，把p的倍数挖掉;
<3> 检查p是否⼩于n^2的整数部分（如果n=1000, 则检查p<31?），如果是，则返回(2)继续执⾏，否则就结束;
<4> 纸上剩下的数就是素数。
这是个典型的⽤空间换时间的算法。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main() {
int i,j,n;
int num = 100;  /*1-100之内的质数，如果求1-10000之间的质数，则num=10000*/
int a[101];  /*数组多定义⼀个元素是为了让下标和数⼀⼀对应，因为数组下标是从0开始的*/        for(int i=0; i<=101; i++) {
a[i] = i;
}      /*初始化数组*/
a[1] = 0;  /*1不是质数*/
for (i=2; i<sqrt(num); i++) {
for (j=i+1; j<=num; j++) {
if (a[j]!=0 && a[j]%i==0) {    /*如果是质数了，则不需要再判断*/
a[j] = 0;    /*a[j]不是质数，故a[j]=0*/
}
}
}  / *依次判断是不是2的倍数，3的倍数，4的倍数。。。。。。。。*/
for(i=1,n=0; i<=100; i++) {
if (a[i] != 0) {
printf("%d\t", a[i]);
c++判断素数if(++n%10 == 0) {
printf("\n");
}
}
}      /*输出a[i]不为0的数（即质数)*/
printf("\n");
return 0;
}

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