判斷101-200之間有多少個素數,并輸出所有素數
??問題分析:題目中的關鍵詞是素數,什么是素數?素數就是只能被1和自身整除的數,例如11就是素數,但12就不是,因為12可以被1,2,3,4,6和12整除,故12就不是素數;但11就只能被1和11整除,所以11就是素數。
??解決辦法:判斷素數的經典方法如下是用一個數分別去除2到sqrt(這個數),如果能被整除,
則表明此數不是素數,反之則是素數。
方法一 根據基本概念編碼
??這里提供一個最基礎版的解題代碼,直接根據概念編碼。
/**
* 素數就是只能被1和自身整除的數
*/
public static void baseSolution() {
int i = 0, count = 0;
for (i = 101; i <= 200; i++) {
if (isPrime(i)) {
count++;
}
}
System.out.println("素數的個數是:" + count);
}
/**
* 判斷一個數是否為素數
*
* @param x 待判定的數
* @return true 是素數
*/
public static Boolean isPrime(int x) {
int s = 0, n;
for (n = 1; n <= x; n++) {
if (x % n == 0) {
s++;
}
}
// s > 2說明被1和本身外的數整除
if (s == 2) {
// 打印素數
System.out.println(x);
return Boolean.TRUE;
}
return Boolean.FALSE;
}
方法二 根據平方根求余數
??記end的平方根的上整數為sqrtEnd,根據數學原理,我們知道只要在[begin, sqrtEnd]中不存在可以整除end的數,則end也為素數。故根據此原理編寫了如下求解源碼:
/**
* 查找 m和n之間的素數
*
* @param begin
* @param end 小于begin時,提示無素數
*/
private static void sqrtSolution(Integer begin, Integer end) {
// 更新步長減少遍歷次數
int len = 1;
if (begin % 2 == 1) {
len = 2;
}
int i = 0, count = 0;
for (i = begin; i <= end; i += len) {
if (isPrimeSqrt(i)) {
count++;
}
}
System.out.println("sqrtSolution 找到的素數個數是:" + count);
}
private static boolean isPrimeSqrt(int x) {
double max = Math.sqrt(x);
boolean b = false;
for (int j = 2; j <= max; j++) {
if (x % j == 0) {
b = Boolean.FALSE;
break;
} else {
b = Boolean.TRUE;
}
}
if (b) {
System.out.println(x);
return b;
}
return Boolean.FALSE;
}
??測試方法就是一個main 函數:
public static void main(String[] args) {
baseSolution();
sqrtSolution(101, 200);
}
讀后有收獲,小禮物走一走,請作者喝咖啡。
Buy me a coffee. ?Get red packets.作者:樓蘭胡楊
本文版權歸作者和博客園共有,歡迎轉載,但請注明原文鏈接,并保留此段聲明,否則保留追究法律責任的權利。

浙公網安備 33010602011771號