Java中判断素数的五种⽅法
Java 中判断素数我们有很多⽅法，每种⽅法时间复杂度也不⼀样。今天我汇总了⼀下，分享给⼤家。既可以输出前 50 或 n 个素数，也可以判断 100 （或 n) 以内的素数。
1. 从 2 到 x-1 测试是否可以整除
Scanner in = new Scanner(System.in);
int x = in.nextInt();
boolean isPrime = true;
if ( x == 1)
{
isPrime = false;
}
for( int i = 2; i< x; i++)
{
if(x % i ==0)
{
isPrime = false;
break;
}
}
if( isPrime)
{
System.out.println(x +"是素数");
}
else
{
System.out.println(x+ "不是素数");
}
2. 去掉偶数后，从 3 到 x-1, 每次加 2
改进版，时间复杂度为 O(n/2)
if(x ==1 || x %2 ==0 && x !=2 )
{
isPrime = false;
}
else
{
for(int i =2; i<x; i +=2)
{
if( x % i == 0)
{
isPrime = false;
break;
}
}
}
if( isPrime)
{
System.out.println(x +"是素数");
}
else
{
System.out.println(x+ "不是素数");
}
3. 2 ⽅法上的改进版，只需到 sqrt(x) 即可以
数学上可以证明，sqrt(x) 即 x 的平⽅根
时间复杂度为 O(sqrt(n))nextint()方法
if(x ==1 || x %2 ==0 && x !=2 )
{
isPrime = false;
}
else
{
for( int i =3; i< Math.sqrt(x); i+=2)
{
if( x % i == 0)
{
isPrime = false;
break;
}
}
}
if( isPrime)
{
System.out.println(x +"是素数");
}
else
{
System.out.println(x+ "不是素数");
}
4. 出前 50 个素数
判断是否能被已知的的且 <x 的素数整除
这个⽅法可扩展性很强，建议掌握。
int [] primes = new int[50];
primes[0] =2;
int cnt =1;
Main:
for(int x= 3; cnt<primes.length; x++)
{
for(int i = 0; i< cnt; i++)
{
if( x % primes[i] == 0)
{
continue Main;
}
}
primes[cnt++] = x;
}
for ( int k: primes)
{
System.out.print(k+ " ");
}
5. ⽤计算机的语⾔去思考
构造素数表，构造 n 以内的素数表
原理：
1. 令 x =2;
2. 将 2x、3x、4x 直⾄ ax<n 的数标记为⾮素数
3. 令 x 为下⼀个没有被标记为⾮素数的数，重复 2；直⾄所有的数都已尝试完毕。
boolean[] isPrime = new boolean[100];
for( int i =2; i< isPrime.length; i++)
{
isPrime[i] = true;
}
for(int i =2; i<isPrime.length; i++)
{
if( isPrime [i])
{
for(int k=2; i*k < isPrime.length; k++)
{
isPrime[i*k] = false;
}
}
}
for( int i = 0; i<isPrime.length; i++)
{
if(isPrime[i])
{
System.out.print(i+ " ");
}
}
好了，以上便是五种判断素数的⽅法，第四种和第五种⽅法要求掌握，相信你能很快学会，⼀定⼀定要上⼿实操，debug ⼀下，你就懂了。
System.out.println(“给我点个赞！”);