快捷導(dǎo)航

Java中判斷素?cái)?shù)的五種有效方法

更新時(shí)間：2026年01月07日 08:28:17 作者：AaronYu_

本文介紹了五種在Java中判斷素?cái)?shù)的有效方法,包括從2到x-1測(cè)試、排除偶數(shù)、僅測(cè)試到sqrt(x),以及使用素?cái)?shù)表和計(jì)算機(jī)思維方式的高級(jí)策略,文章詳細(xì)解釋了每種方法的時(shí)間復(fù)雜度和實(shí)現(xiàn)細(xì)節(jié),需要的朋友可以參考下

1. 從 2 到 x-1 測(cè)試是否可以整除

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 +"是素?cái)?shù)");
	
}
else
{
	System.out.println(x+ "不是素?cái)?shù)");
}

2. 去掉偶數(shù)后，從 3 到 x-1, 每次加 2

改進(jìn)版，時(shí)間復(fù)雜度為 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 +"是素?cái)?shù)");
	
}
else
{
	System.out.println(x+ "不是素?cái)?shù)");
}

3. 2 方法上的改進(jìn)版，只需到 sqrt(x) 即可以

數(shù)學(xué)上可以證明，sqrt(x) 即 x 的平方根
時(shí)間復(fù)雜度為 O(sqrt(n))

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 +"是素?cái)?shù)");	
}
else
{
	System.out.println(x+ "不是素?cái)?shù)");
}

4. 找出前 50 個(gè)素?cái)?shù)

判斷是否能被已知的的且 <x 的素?cái)?shù)整除
這個(gè)方法可擴(kuò)展性很強(qiáng)，建議掌握。

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. 用計(jì)算機(jī)的語(yǔ)言去思考

構(gòu)造素?cái)?shù)表，構(gòu)造 n 以?xún)?nèi)的素?cái)?shù)表

原理：

令 x =2;
將 2x、3x、4x 直至 ax<n 的數(shù)標(biāo)記為非素?cái)?shù)
令 x 為下一個(gè)沒(méi)有被標(biāo)記為非素?cái)?shù)的數(shù)，重復(fù) 2；直至所有的數(shù)都已嘗試完畢。

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+ " ");
	}
}

好了，以上便是五種判斷素?cái)?shù)的方法，第四種和第五種方法要求掌握，相信你能很快學(xué)會(huì)，一定一定要上手實(shí)操，debug 一下，你就懂了。

到此這篇關(guān)于Java中判斷素?cái)?shù)的五種有效方法的文章就介紹到這了,更多相關(guān)Java判斷素?cái)?shù)方法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: