必背C语言算法 求素数的几种方法

素数又称质数。所谓素数是指除了 1 和它本身以外，不能被任何整数整除的数，例如17就是素数，因为它不能被 2~16 的任一整数整除。

思路1)：因此判断一个整数m是否是素数，只需把 m 被 2 ~ m-1 之间的每一个整数去除，如果都不能被整除，那么 m 就是一个素数。

思路2)：另外判断方法还可以简化。m 不必被 2 ~ m-1 之间的每一个整数去除，只需被 2 ～根号m 之间的每一个整数去除就可以了。如果 m 不能被 2 ~ 根号m 间任一整数整除，m 必定是素数。例如判别 17 是是否为素数，只需使 17 被 2~4 之间的每一个整数去除，由于都不能整除，可以判定 17 是素数。

原因：因为如果 m 能被 2 ~ m-1 之间任一整数整除，其两个因子必定有一个小于或等于 图片，另一个大于或等于 根号m。例如 16 能被 2、4、8 整除，16=28，2 小于 4，8 大于 4，16=44，4=√16，因此只需判定在 2~4 之间有无因子即可。【减少运算时间】
思路1代码（经常考填空题）：

#include <stdio.h>
int main(){
    int num,i;  
    printf("输入一个整数：");
    scanf("%d",&num);// 输入的整数
    for(i=2;i<num;i++){
        if(num%i==0)
          break;
    }
    if(i>=num)//i的范围是从2开始到num，如果num不是素数,i的值一定小于num 
        printf("%d是素数。\n", num);
    else
        printf("%d不是素数。\n", num);
    return 0;
}

思路1代码（另一种思路）：

#include <stdio.h> 
int pri(int n) {
    if(n<2)//最小的素数为2 小于2的都是不是素数 
    return 0;  
  int i;
    for (i=2;i<=n/2; i++) {
        if (n%i == 0)
          return 0;//不是素数直接返回0
    }
    return 1;//是素数返回1
}
int main(){
    int num;
  scanf("%d",&num);
  if(pri(num))
    printf("%d是素数",num);
  else
    printf("%d不是素数",num);
}

思路2代码【运算最省时间的代码】：

#include <stdio.h>
#include <math.h>
void main(){
    int m;  // 输入的整数 
    int i;  // 循环次数
    int k;  // m 的平方根 
    printf("输入一个整数：");
    scanf("%d",&m);
    // 求平方根，注意sqrt()的参数为 double 类型，这里要强制转换m的类型 
    k=(int)sqrt( (double)m );
    for(i=2;i<=k;i++)
        if(m%i==0)
            break;
    // 如果完成所有循环，那么m为素数
    // 注意最后一次循环，会执行i++，此时 i=k+1，所以有i>k 
    if(i>k)
        printf("%d是素数。\n",m);
    else
        printf("%d不是素数。\n",m);

    return 0;
}

【补充】求一个范围内的素数是以下代码：

#include<stdio.h>
int main(){
  int i,k,num;
  printf("求多少以内的素数呢？\n");
  scanf("%d",&num); 
  //需要循环嵌套 
  for(i=2;i<=num;i++)
  {
    int p=1; //用p来判断当前数是否是质数 ，p=1是质数,p=0不是质数
    for(k=2;k<i;k++)
    {
      if(i % k == 0)
      {
        p=0;
        break;
      }
    }
    if(p == 1)
      printf("%d ",i);  
  }
}