① java語言：請輸入一個整數，並判斷他是否為素數 急！！ 正在考試
1. 根據概念判斷:
如果一個正整數只有兩個因子, 1和p，則稱p為素數.
public boolean isPrime(int n)
{
if(n < 2) return false;
for(int i = 2; i < n; ++i)
if(n%i == 0) return false;
return true;
}
時間復雜度O(n).
2. 改進, 去掉偶數的判斷
public boolean isPrime(int n)
{
if(n < 2) return false;
if(n == 2) return true;
if(n%2==0) return false;
for(int i = 3; i < n; i += 2)
if(n%i == 0) return false;
return true;
}
時間復雜度O(n/2), 速度提高一倍.
3. 進一步減少判斷的范圍
定理: 如果n不是素數, 則n有滿足1< d<=sqrt(n)的一個因子d.
證明: 如果n不是素數, 則由定義n有一個因子d滿足1< d< n.
如果d大於sqrt(n), 則n/d是滿足1< n/d<=sqrt(n)的一個因子.
public boolean isPrime(int n)
{
if(n < 2) return false;
if(n == 2) return true;
if(n%2==0) return false;
for(int i = 3; i*i <= n; i += 2)
if(n%i == 0) return false;
return true;
}
時間復雜度O(Math.sqrt(n)/2), 速度提高O((n-Math.sqrt(n))/2).
4. 剔除因子中的重復判斷.
定理: 如果n不是素數, 則n有滿足1< d<=Math.sqrt(n)的一個"素數"因子d.
證明: I1. 如果n不是素數, 則n有滿足1< d<=Math.sqrt(n)的一個因子d.
I2. 如果d是素數, 則定理得證, 演算法終止.
I3. 令n=d, 並轉到步驟I1.
由於不可能無限分解n的因子, 因此上述證明的演算法最終會停止.
// primes是遞增的素數序列: 2, 3, 5, 7, ...
// 更准確地說primes序列包含1->Math.sqrt(n)范圍內的所有素數
public boolean isPrime(int primes[], int n)
{
if(n < 2) return false;
for(int i = 0; primes[i]*primes[i] <= n; ++i)
if(n%primes[i] == 0) return false;
return true;
}
5. 構造素數序列primes: 2, 3, 5, 7, ...
由4的演算法我們知道, 在素數序列已經被構造的情況下, 判斷n是否為素數效率很高;
下面程序可以輸出素數表.
public class ShowPrimeNumber{
public static int[] getPrimeNums(int maxNum){
int[] primeNums = new int[maxNum/2+1];
int sqrtRoot;
int cursor = 0;
boolean isPrime;
for(int i=2;i<=maxNum;i++){
sqrtRoot = (int)Math.sqrt(i); //取平方根
isPrime = true;
for(int j=0;j< cursor;j++){
if(primeNums[j]>sqrtRoot)
break;
if(i%primeNums[j]==0){
isPrime = false;
break;
}
}
if(isPrime){
primeNums[cursor++] = i;
}
}
int[] result = new int[cursor];
System.array(primeNums,0,result,0,cursor);
return result;
}
public static void main(String[] args) throws Exception{
int maxNum = Integer.parseInt(args[0]);
int[] primeNums = getPrimeNums(maxNum);
System.out.println("共"+primeNums.length+"個素數");
for(int i=0;i< primeNums.length;i++){
System.out.print(primeNums[i]+",\t");
}
}
}
6.(在素數表中)二分查找
Arrays.BinarySearch方法:
該方法用於在指定數組中查找給定的值，採用二分法實現，所以要求傳入的數組已經是排序了的。
該方法的基本語法格式為：
Static int binarySearch(byte[] a, byte key)
該方法返回數據中key元素所在的位置，如果沒有key元素，則返回key應插入的位置：-（insertion point-1），如數組中的第一個元素就大於key，返回-1。
註：數組的數據類型可以是int[] byte[] short[] float[] long[] double[] char[] Object[]類型。
② JAVA 輸入一個數判斷其是否是素數
public class panansushu {
public static void main(String args[]) {
int x, y, j;
Scanner i = new Scanner(System.in);
System.out.print("請輸入一個數：");
y = i.nextInt();
j = (int) y / 2;
for (x = 2; x <= j; x++) {
if (y % x == 0) {
System.out.println("此數不為素數");
break;
}
}
if (x > j) {
System.out.println("此數為素數");
}
}
}
③ java中怎麼求素數
首先樓主應該對素數的定義已經清楚了吧?其實就是一個數,如果存在1和它本身以外,有數能整除它,這個數就不是素數.
在這里,有2個關鍵的變數,我估計解釋一下你就能看得明白這個演算法了.
1.關於變數k.變數k的作用是優化整個演算法,因為比如要判斷一個數13是不是素數,我們沒必要從2循環到13.只要循環到對13開根號.13開根號大概是3.6多,強轉為int類型後是3.也就是說只要檢查2,3是否能整除13.如果不能,13肯定是一個素數.因為比如48這個數,你前面檢測到被4整除等於12,那麼繼續循環超過Math.sqrt(48)的話,無非就是得到一個反過來的被12除等於4的結果.這個沒有必要.
2.關於變數j.注意點1:j是在最外層的循環體中定義的.這個時候剛定義完,j的值是初始的0.然後j從2開始,一直到小於等於k結束.這里是控制嘗試整除的循環次數.一旦發現在這個范圍內有數能整除i,那麼就跳出循環.
所以,對於你不理解的那個部分,首先確定一點,程序只要執行到break,就說明這個數是素數.
例如我們這次k = 10,那麼是要從j = 2到10逐一檢測 i 是不是能被 j 整除.當j = 7的時候比如可以整除了,就跳出當前內層循環了.這時候, j 顯然是不大於 k 的,因為只要是中途跳出,因為內層循環(j = 2; j <= k; j++)的控制,只要在循環過程中跳出來的,那麼j 肯定 <= k.
只有循環到j = 10依然沒有break的話,根據for循環的執行順序,會執行j++,然後去判斷j <= k 是否為true,為true則繼續下一次循環,否則循環結束.而在這里,如果到10還沒有能夠整除的話,j是會在10的基礎上自增的.這時候j就=11了.
那麼if ( j > k )就不成立了,則i 不會被輸出.
總結一點:就是如果中途or最後一次循環,找到能整除的數了,那麼因為break的關系,最後就不會執行 j++, 所以j <= k的條件是能保證的. 換言之,如果j > k (亦即j <= k 的取反)表示沒有找到能整除的數.其實j最大也就只能等於k+1.
另外,,你也可以自己修改修改,來加深理解.例如
boolean isPrime; //定義布爾變數判斷是否素數.是:true;否:false
for (int i = 3; i <= 100; i++) {
isPrime = true;
int k = (int) Math.sqrt(i);
for (int j = 2; j <= k; j++) {
if (i % j == 0) {
isPrime = false; //如果能夠有數整除i,那麼就不是素數.
break;
}
}
if (isPrime) {
System.out.println(i);
}
}
這樣就沒有必要在外層循環里就定義j這個變數了.如果我上面說的你理解還是比較困難,可以先理解用布爾變數來控制的寫法.這個理解了,用j > k 判斷的就也很容易理解了.
④ 用java語言判斷一個數是不是質數
下面是我用JavaScript寫的素數函數，供參考，大同小異
PrimeA=function(n,nth){/* 小於n的素數表
參數nth 指定返回第n個素數
*/
//vart0=Time.now5();
/*
方法1：利用isPrime 廢棄！
vart=[];
for(vari=2;i<n+1;i++){
if(isPrime(i)){
t.push(i)
}
}
consolelog('方法1：耗時：'+(+Time.now5()-(+t0)));
returnt
*/
//方法2：利用篩法
varp=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59];//自己往後補充，越多越好，可以加快檢測小素數的效率
if(nth&&n<=669){
returnp[n-1]
}
if(!nth&&n<2){
return[]
}
if(n<=5000&&!nth){
for(vari=0;i<100;i++){
varj=p.indexOf(n-i);
if(j>-1){returnp.slice(0,j+1)};
}
returnp
}
varm=nth?Math.ceil(n*Math.log(n)+1000):n; //pn∼nln(n)
// for(vari=5001;i<=m;i+=2){
vari=5001;
while(i){
vart=Math.floor(Math.sqrt(i)),pl=p.length;
for(varj=0;j<pl;j++){//p.length
if(i%p[j]==0){
break
}elseif(p[j+1]>t){
p.push(i);
if(nth&&pl==n-1){
returni
}
break;
}
}
if(!nth&&i>=n-1){
returnp
}
i+=2;
}
returnp
//方法3：Wilson測試
}