作者peacedove (林帛亨加油！！！)
看板java
標題Re: [問題] 搜尋質數
時間Sun Jul 3 03:25:57 2011
用你的code下去稍微修改
黃色為我有修改的部份
現在精神狀況不太好(好想睡) 希望沒有改錯
當然一定有更好的演算法啦XD
class TestPrime
{
// 一維陣列的應用:求質數
public static void main(String args[])
{
final int MAX = 300;// Once it is initiated it can not be changed.
// false為質數,true為非質數
// 宣告後若沒有給定初值,其預設值為false
boolean prime[] = new boolean[MAX];
prime[0] = true;
prime[1] = true;// 0 and 1 are not prime;
int count = 0;
for (int i = 2; i < MAX; i++)
{
prime[i] = false;
for (int a = 2; a*a <= i; a++)
{
if (i % a == 0)
{
prime[i] = true;
break;
}
}
}
for (int i = 2; i < MAX; i++)
{
if (prime[i] == false)
{
count++;
System.out.println(i);
}
}
System.out.println("the number of prime is " + count);
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.135.51.171
※ 編輯: peacedove 來自: 220.135.51.171 (07/03 03:37)
※ 編輯: peacedove 來自: 220.135.51.171 (07/03 11:22)
→ Nozaki:感謝！！！終於可以跑了QQ 07/03 22:00
推 Nozaki:請問一下那個for回圈為什麼是用a*a<=i, 而不是a<i就可以呢? 07/03 22:02
推 qqwwee33:迴圈可以跑比較少圈吧 07/03 23:53
推 nameyi:如果有因數的話會是兩兩成對 所以只要測完前面一半就足夠了 07/04 13:14
推 shiengchyi:其實可以跑得更少 07/04 14:41
→ shiengchyi:判斷 2 3 5 7 9 11 13....<= Num/2 2以外的偶數不用測 07/04 14:43
→ shiengchyi:打錯 XD 是 floor(pow(Num,0.5)) 不是Num/2 07/04 14:47
→ peacedove:是啊 可是程式碼要改動太多了 就算了 07/04 18:26
→ peacedove:其實2跟3的倍數都可以跳過 07/04 18:29
→ peacedove:還有只要檢查質數之類的 07/05 03:22
推 shiengchyi:只要檢查質數這件事本身就沒什麼意義 07/06 14:59
→ shiengchyi:1是質數本身沒有規律 2.是過濾的數量 去掉偶數就少一半 07/06 15:01
→ peacedove:用個arraylist就可以解決質數本身沒規律的問題啦 07/06 15:17
→ peacedove:相關的演算法討論 之前板上就有討論過了 07/06 15:19