1是素数吗

判断⼀个数是否是素数

判断⼀个数是否是素数

⼀、判断⼀个数是否是素数？

publicbooleanisPrimeNumber(intnum){

if(num==2)returntrue; //2特殊处理

if(num<2||num%2==0)returnfal; //识别⼩于2的数和偶数

for(inti=3;i<=(num);i+=2){

if(num%i==0){ //识别被奇数整除

returnfal;

}

}

returntrue;

}

质数的定义：质数（primenumber）⼜称为素数，有⽆限多个。质数定义在⼤于1的⾃然数中，除了1和它本⾝以外不会再有其它

因数的数称为质数。（1）从2开始，2是最⼩的质数。（2）除了2之外的偶数全都不是质数，因为除了1和⾃⾝之外它们还能被

2整除。若为⼤于2的奇数，则进⼊下⼀步继续判断。（3）将其开⽅，若从3到开⽅向下取整之间的所有奇数都不能将其整除，

则说明该数为质数。⾄于为什么只⽤除到其平⽅根？因为如果⼀个数不是素数是合数，那么⼀定可以由两个⾃然数相乘得到，

其中⼀个⼤于或等于它的平⽅根，⼀个⼩于或等于它的平⽅根。

⼆、三种素数之间的⽐较？

packageJava基础;

publicclassTestPrime{

publicstaticvoidmain(String[]args){

longstartTime1=tTimeMillis();

for(inti=1;i<=100;i++){

if(isPrime1(i)){

(i+"");

}

}

longendTime1=tTimeMillis();

n("⽅式⼀消耗时间："+(endTime1-startTime1));

longstartTime2=tTimeMillis();

for(inti=1;i<=100;i++){

if(isPrime2(i)){

(i+"");

}

}

longendTime2=tTimeMillis();

n("⽅式⼆消耗时间："+(endTime2-startTime2));

longstartTime3=tTimeMillis();

for(inti=1;i<=100;i++){

if(isPrime3(i)){

(i+"");

}

}

longendTime3=tTimeMillis();

n("⽅式三消耗时间："+(endTime3-startTime3));

}

/*

*1.根据概念判断:

如果⼀个正整数只有两个因⼦,1和p，则称p为素数.

时间复杂度O(n).

*/

publicstaticbooleanisPrime1(intn){

if(n<2)

returnfal;

for(inti=2;i

if(n%i==0)

returnfal;

returntrue;

}

/*

*2.改进,去掉偶数的判断

时间复杂度O(n/2),速度提⾼⼀倍.

*/

publicstaticbooleanisPrime2(intn){

if(n<2)

returnfal;

if(n==2)

returntrue;

if(n%2==0)

returnfal;

for(inti=3;i

if(n%i==0)

returnfal;

returntrue;

}

/*

*3.进⼀步减少判断的范围

定理:如果n不是素数,则n有满⾜1

证明:如果n不是素数,则由定义n有⼀个因⼦d满⾜1

如果d⼤于sqrt(n),则n/d是满⾜1

时间复杂度O((n)/2),速度提⾼O(((n))/2).

*/

publicstaticbooleanisPrime3(intn){

if(n<2)

returnfal;

if(n==2)

returntrue;

if(n%2==0)

returnfal;

for(inti=3;i*i<=n;i+=2)

if(n%i==0)

returnfal;

returntrue;

}

}

三、质数检测

给出N个正整数，检测每个数是否为质数。如果是，输出"Yes"，否则输出"No"。

Input

第1⾏：⼀个数N，表⽰正整数的数量。(1<=N<=1000)

第2-N+1⾏：每⾏1个数(2<=S[i]<=10^9)

Output

输出共N⾏，每⾏为Yes或No。

Input⽰例

5

2

3

4

5

6

Output⽰例

Yes

Yes

No

Yes

No

Java代码

r;

publicclassMain{

publicstaticvoidmain(String[]args){

Scannerscan=newScanner();

intn=t();

int[]nums=newint[n];

intm=0;

while(n--!=0){

nums[m++]=t();

}

for(inti:nums){

if(isPrime(i)){

n("Yes");

}el{

n("No");

}

}

}

publicstaticbooleanisPrime(intn){

if(n<2)returnfal;

if(n==2)returntrue;

if(n%2==0)returnfal;

for(inti=3;i*i<=n;i++){

if(n%i==0)

returnfal;

}

returntrue;

}

}

四、找出0-50之间的所有素数，所谓素数就是只能被1和它本⾝整除的数字，⽐如：7，13，23等。

#include

intmain()

{

intm,n;

for(m=2;m<=50;m++)

{

for(n=2;n

{

if(m%n==0)//什么条件下跳出当前循环

break;//这⾥应该退出当前循环了

}

if(m==n)//n循环结束后，如果m=n的话就输出m

printf("%d",m);

}

return0;

}

参考资料