判断素数的几种方法

设计程序判断素数,经过总结,有如下常见方法:

方法一:

#include<stdio.h>
int main() {
 int x=0,isprime=1;
 scanf(\"%d\",&x);
 for(int i=2;i<x;++i) {
  if(x%i==0) {
   isprime=0;
   break;
  }
 }
 if(isprime==1) {
  printf(\"素数\");
 } else {
  printf(\"非素数\");
 }
 return 0; 
}

== 这种方式最常用,安全 ==

方法二:

#include<stdio.h>
int main() {
 int x=0,i=0;
 scanf(\"%d\",&x);
 for(i=2;i<x;++i) {
  if(x%i==0) {
   break;
  }
 }
 if(i==x) {
  printf(\"素数\\n\"); 
 } else {
  printf(\"非素数\\n\"); 
 }
 return 0; 
}

== 这种方法看似聪明,但是实际上这种方法并不推荐,因为这种代码影响程序的可读性,设置第三变量会保证程序安全性 ==

方法三:

其实如果要判断输入的x是否为素数,无须判断到x-1,到sqrt(x)就够了!

#include<stdio.h>
#include<math.h>
int main() {
 int x=0,isprime=1;
 scanf(\"%d\",&x);
 //大于2的偶数一定为非素数
 if(x<2||x%2==0&&x!=2) {
  isprime=0;
 }
 //由于已经去掉了所有偶数,剩下的数一定不能被偶数整除
 //所以此处可以直接从3开始判断,每次加2判断是否能整除
 for(int i=3;i<sqrt(x);i+=2) {
  if(x%i==0) {
   isprime=0;
   break;
  }
 }
 if(isprime==1) {
  printf(\"素数\");
 } else {
  printf(\"非素数\");
 }
 return 0;
}

== 这种方法运算次数少,速度快,但是代码较为复杂不易理解 ==

方法四:

我们可以反一个方向看待这个问题,我们不是去判断它是不是素数,而是去构造一张素数表

#include<stdio.h>
int main() {
 //构造n以内(不含n)的素数表 
 //1.开辟isPrime[n],初始化其所有元素为1,isPrime[x]为1代表素数 
 //2.令x=2 
 //3.如果x是素数,则对于(i=2;x*i<n;i++)令isPrime[i*x]=0 
 //4.令x++,如果x<n,重复3,否则结束 
 const int maxNumber=100; 
 int isPrime[maxNumber],i,x;
 for(i=0;i<maxNumber;i++) {
  isPrime[i]=1;
 }
 for(x=2;x<maxNumber;x++) {
  if(isPrime[x]) {
   for(i=2;i*x<maxNumber;i++) {
    isPrime[i*x]=0;
   }
  }
 }
 //打印被赋值为1的(即素数)下标 
 for(i=2;i<maxNumber;i++) {
  if(isPrime[i]) {
   printf(\"%d\\t\",i);
  }
 }
 printf(\"\\n\");
 return 0;
}