Java中判斷素數(shù)的五種有效方法
更新時間：2026年01月07日 08:28:17 作者：AaronYu_
本文介紹了五種在Java中判斷素數(shù)的有效方法,包括從2到x-1測試、排除偶數(shù)、僅測試到sqrt(x),以及使用素數(shù)表和計算機思維方式的高級策略,文章詳細解釋了每種方法的時間復雜度和實現(xiàn)細節(jié),需要的朋友可以參考下
Java 中判斷素數(shù)我們有很多方法，每種方法時間復雜度也不一樣。今天我匯總了一下，分享給大家。既可以輸出前 50 或 n 個素數(shù)，也可以判斷 100 （或 n) 以內(nèi)的素數(shù)。
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 +"是素數(shù)");
}
else
{
System.out.println(x+ "不是素數(shù)");
}
2. 去掉偶數(shù)后，從 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 +"是素數(shù)");
}
else
{
System.out.println(x+ "不是素數(shù)");
}
3. 2 方法上的改進版，只需到 sqrt(x) 即可以
數(shù)學上可以證明，sqrt(x) 即 x 的平方根
時間復雜度為 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 +"是素數(shù)");
}
else
{
System.out.println(x+ "不是素數(shù)");
}
4. 找出前 50 個素數(shù)
判斷是否能被已知的的且 <x 的素數(shù)整除
這個方法可擴展性很強，建議掌握。
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. 用計算機的語言去思考
構造素數(shù)表，構造 n 以內(nèi)的素數(shù)表
原理：
- 令 x =2;
- 將 2x、3x、4x 直至 ax<n 的數(shù)標記為非素數(shù)
- 令 x 為下一個沒有被標記為非素數(shù)的數(shù)，重復 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+ " ");
}
}
好了，以上便是五種判斷素數(shù)的方法，第四種和第五種方法要求掌握，相信你能很快學會，一定一定要上手實操，debug 一下，你就懂了。
到此這篇關于Java中判斷素數(shù)的五種有效方法的文章就介紹到這了,更多相關Java判斷素數(shù)方法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了SpringBoot 編寫配置文件的兩種方法，幫助大家更好的理解和使用springboot框架，感興趣的朋友可以了解下2020-11-11
SpringCloud OpenFeign與Ribbon客戶端配置詳解
在springcloud中，openfeign是取代了feign作為負載均衡組件的，feign最早是netflix提供的，他是一個輕量級的支持RESTful的http服務調(diào)用框架，內(nèi)置了ribbon，而ribbon可以提供負載均衡機制，因此feign可以作為一個負載均衡的遠程服務調(diào)用框架使用2022-11-11
這篇文章主要介紹了window中使用bat啟動springboot項目，并解決亂碼問題2021-06-06
很多時候我們需要根據(jù)不同的條件在容器中加載不同的Bean，或者根據(jù)不同的條件來選擇是否在容器中加載某個Bean，這就是Bean的加載控制，一般我們可以通過編程式或注解式兩種不同的方式來完成Bean的加載控制2023-02-02
Java面試題之this 和 super 的區(qū)別解析
this 和 super 雖然都是Java中的關鍵字,但它們的作用和使用場景有著明顯的區(qū)別,下面給大家介紹Java面試題之this 和 super 的區(qū)別解析,感興趣的朋友一起看看吧2025-05-05
這篇文章主要介紹了HashMap源碼中的位運算符&詳解，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-07-07
這篇文章主要介紹了Springboot如何加載靜態(tài)圖片，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-03-03
這篇文章主要介紹了關于IDEA中Maven項目中JSTL標簽無效問題的解決方法,需要的朋友可以參考下2018-09-09
本篇文章主要介紹了mybatis高級映射一對多查詢實現(xiàn)代碼，具有一定的參考價值，感興趣的小伙伴們可以參考一下。2017-04-04
今天帶大家學習Java常用工具類,文中有非常詳細的圖文解說及代碼示例,對正在學習java的小伙伴們很有幫助,需要的朋友可以參考下，希望能給你帶來幫助2021-07-07