基本概念

如何判断素数(判断素数的一种简单算法（C） 判断一个实数是不是素数的算法（C\\C++）： 最简洁的素数判断方法(C/C++版本） 效率比较高的素数判断方法（C++版本） 判断素数其他代码)

基本概念

素数（又称质数）：

就是除了1和它本身，没有其他因子的整数。

注：1既不是素数，也不是合数。

如何判断素数

判断素数的一种简单算法（C）

素数即只能被1和其本身整除的数，判断n是否为素数只需用2~n/2之间的数去除就可以了。因为一个数的一半的平方大于其本身是从5开始的，解方程：n/2的平方>n 。即一个数n的两个因数不能同时比n/2大。就可以说一个数若不是素数则一定在2~n/2之间有因数。而且2，3也是符合下面程序的。

#include <stdio.h>

main(){

int i,j,k=0;

for(i=2;i<=1000;i++)

{

for(j=2;j<=i/2;j++)

if(i%j==0)break;

if(j>i/2)

{

printf("%d ",i);

}

}}

判断一个实数是不是素数的算法（C\\C++）：

例如 17是素数，因为它不能被2~16间

任意一整数整除。因此判断一个整数m是否为素数，只需用2~m-1之间的每一个整数去除，如果都不能被整除，那么m就是一个素数。

其实可以简化，m不必被2~m-1之间的每一个整数去除，只需被2~根号m之间的每个数去除就可以了。例如判别17是否为素数，只需使2~4之间的每一个整数去除。为什么可以做如此简化呢？因为如果m能被2~m-1之间任意整数整除，如果这个数大于根号m，那这个数必定对应的还有一个比根号m小的因子（以16为例，2、8是它的因子，8大于4，2小于4）。

写了一个判断素数的函数，和大家分享。

//写一个能判断是否是素数的函数

#include <stdio.h>

#include <math.h>

#define TRUE 1

#define FALSE 0

void main(){

int n;

unsigned char judgePrime(int n);

printf("Input a number:\");

scanf("%d",&n);

if (judgePrime(n)==TRUE) {

printf("TRUE\");

}

else{

printf("FALSE\");

}

}

unsigned char judgePrime(int n){

int i;

unsigned char judge = TRUE;

if (n==2) {

judge = TRUE;

}

else if(n>2){

if (n%2==0) {

judge = FALSE;

}

else{

for (i=3;i<=sqrt(n);i+=2)

{

if (n%i==0)

{

judge = FALSE;

break;

}

}

}

}

else

{

judge = FALSE;

}

return judge;

}

最简洁的素数判断方法(C/C++版本）

bool prime(int n)

{

int a=2;

while (a<n)

if (!(n%a++)) break;

if (a==n) return 1;

return 0;

}

注:1. 返回值1,表示该数为素数.

2.该函数可在c和c++使用,bool为布尔顿型,也可以改为int型.

效率比较高的素数判断方法（C++版本）

#include<iostream>

#include<cmath>

using namespace std;

bool prime( int num)

{

if (num==2||num==3||num==5) return true;

unsigned long c=7;

if (num%2==0||num%3==0||num%5==0||num==1) return false;

int maxc=int(sqrt(num));

while (c<=maxc)

{

if (num%c==0) return false;

c+=4;

if (num%c==0) return false;

c+=2;

if (num%c==0) return false;

c+=4;

if (num%c==0) return false;

c+=2;

if (num%c==0) return false;

c+=4;

if (num%c==0) return false;

c+=6;

if (num%c==0) return false;

c+=2;

if (num%c==0) return false;

c+=6;

}

return true;

}

int main()

{

int num;

cin>>num;

if (prime(num)) cout<<num<<" is a prime number."<<endl;

else cout<<num<<" is not a prime number."<<endl;

return 0;

}

判断素数其他代码

代码一：

#include<iostream.h>

#include<math.h>

void zhishu(int n)

{

int i,s=1,t;

int w;

w=sqrt(n);//sqrt函数的函数头是math.h

for(i=2;i<=w;i++)

{

t=n%i;

if(t!=0)t=1;

s=s*t;

}

if(s)cout<<n<<'\\t';

}

void main(void)

{int k,j;

cin>>k;//输入2000，输出2000以内所有素数

for(j=2;j<=k;j++)

zhishu(j);

}

代码二：

#include<iostream>

#include<math.h>

using namespace std;

int main(void)

{

int isprimer(int num);

int x,point;

cout<<"Please enter a integer number(请输入一个正整数):"<<endl;

cin>>x;

point=isprimer(x);

if(point)

cout<<x<<" is a prime.("<<x<<"是素数)"<<endl;

else

cout<<x<<" is not a prime.("<<x<<"不是素数)"<<endl;

return 0;

}

int isprimer(int num)

{

int i,k;

k=sqrt(num);

for(i=2;i<=k;i++)

if(num%i==0)break;

if(i>=k+1&&num!=1)

return 1;

else

return 0;

}