893
技術社區[雲棲]
素數是個什麼東西 prime number
import java.util.ArrayList;
import java.util.Scanner;
public class PrimeNumber {
/**
* *********************************************************************
* 隻有1和它本身兩個正因數的自然數，叫質數(Prime Number)。
* （如：由2÷1=2，2÷2=1，可知2的因數隻有1和它本身2這兩個約數，所以2就是質數。
* 與之相對立的是合數：“除了1和它本身兩個因數外，還有其它因數的數，叫合數。”
* 如：4÷1=4，4÷2=2，4÷4=1，很顯然，4的因數除了1和它本身4這兩個因數以外，還有因數2，所以4是合數。）
* 100以內的質數有2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，
* 73，79，83，89，97，在100內共有25個質數。
* 注：（1）2和3是所有素數中唯一兩個連著的數。
* （2）2是唯一一個為偶數（雙數）的質數。[1]
* 質數的平方數隻有三個因數.
* ********************************************************************
* @param args
* 題目：判斷101-200之間有多少個素數，並輸出所有素數。
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
//根據輸入的兩個數，輸出兩數之間的全部素數
int start = 0, end = 0;
Scanner input = new Scanner(System.in);
System.out.println(" 請輸入大於1的兩個數區間 ");
while(start <= 1 || end <= 1){
try{
start = input.nextInt();
end = input.nextInt();
}catch(Exception e){}
}
input.close();
ArrayList list = new ArrayList();//保存判斷出來的素數
for(int i = start; i <= end; i++){
if(isPrime(i)){
list.add(i);
}
}
System.out.println(start + " 到 " + end + " 之間的素數是 " + list + "\n總數是 " + list.size());
}
/**
*
* @param int number
* @return boolean (true is prime number, false is not prime number);
*/
private static boolean isPrime(int i){
int k = (int) Math.sqrt(i);
if (i < 3 && i > 0)
return true;//2、3是唯一連續的兩個素數
for (int j = 2; j < i/2+1; j++){
if(i%j == 0) //如果餘數為0，表示被1和自己之外的數整除了，即非素數，屬於合數
return false;
}
return true;
}
}
根據素數定義，判斷一下，除了1和本身之外的數字，隻要不能把本身整除，那麼證明這個數字就是素數了。
因此想要從1到數字本身一次判斷餘數是否為0，
然後又想，當循環超過數字本身一半之後就已經不可能在有整除的情況出現了，因此，循環可以減少一些，控製條件改正 本身除以2
但是對於4這樣的小數的時候有問題，因此修改為 本身/2+1，這樣可以了。
看到很多地方使用的是 Math.sqrt(本身); 表示不明所以。
最後更新：2017-04-03 12:54:00