『壹』 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求素數：for(j=2;j<=i/2;j++):是什麼意思為什麼i/2，為什麼沒有「{」
如上所述，不加{}的for的循環體只有後面緊接的一句，
為什麼是i/2，就是i的一半（呵呵貌似白說了哈），當i的一半賦給一個整型的數時，或i/2被當成一個整型的數使用時，它一半就是去掉小數後的數（向下取整，比如5的一半，就當是2）
因此，演算法大致的意思是這樣，一個3到100的數，如果這個數，都不能被2到這個數的一半的數整除的話，就是素數
------------以下是對補充問題的回答------------------------
第一個if，當i能被j（一個2到i一半的整數）整除的時候，跳出for(j=2;j<=i/2;j++){}循環體，當然for(j=2;j<=i/2;j++){}循環體什麼也沒做，就一個勁的判斷，當判斷到有的場合時跳出，沒有的話，j遞增，然後繼續循環
直到循環結束都沒出現當i能被j（一個2到i一半的整數）整除的場合時，也跳出循環體，而j的值在結束時加1，剛好大過或等於（i的一半加1）。
而i在以上的兩種情況跳出的場合，性質是不一樣的，第一種是非素數，第二種是素數，所以進行
第二個if，假如for(j=2;j<=i/2;j++){}循環體是在循環還沒結束時跳出的，值必定小於（i的一半加1），就什麼也不做，反之，是在循環結束時跳出的，那就是素數，就進行列印，
第三個if，沒用{}那麼隻影響下一句，效果就是每6個素數就分別多用一行空行格開，純粹格式不用在意
當然，如樓上，所說可以用i的平方根代替，可以減少檢驗次數
可能沒說清楚，可能啰嗦了點，呵呵，希望對你有幫助！
-------------------------------對補充的回答
這兩天沒上網XD，是的，沒有自增
『叄』 java for循環 求素數
importjava.io.*;
classtest
{
publicstaticvoidmain(String[]args)throwsjava.lang.Exception
{
for(intn=2;n<100;n++){
booleanflag=true;
for(intm=2;m<n;m++){
if(n%m==0){
flag=false;
break;
}
}
if(flag){
System.out.println(n);
}
}
}
}
你自己看下吧，兩個for實現。