作者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)
1F：→ Nozaki:感谢！！！终於可以跑了QQ 07/03 22:00
2F：推 Nozaki:请问一下那个for回圈为什麽是用a*a<=i, 而不是a<i就可以呢? 07/03 22:02
3F：推 qqwwee33:回圈可以跑比较少圈吧 07/03 23:53
4F：推 nameyi:如果有因数的话会是两两成对 所以只要测完前面一半就足够了 07/04 13:14
5F：推 shiengchyi:其实可以跑得更少 07/04 14:41
6F：→ shiengchyi:判断 2 3 5 7 9 11 13....<= Num/2 2以外的偶数不用测 07/04 14:43
7F：→ shiengchyi:打错 XD 是 floor(pow(Num,0.5)) 不是Num/2 07/04 14:47
8F：→ peacedove:是啊 可是程式码要改动太多了 就算了 07/04 18:26
9F：→ peacedove:其实2跟3的倍数都可以跳过 07/04 18:29
10F：→ peacedove:还有只要检查质数之类的 07/05 03:22
11F：推 shiengchyi:只要检查质数这件事本身就没什麽意义 07/06 14:59
12F：→ shiengchyi:1是质数本身没有规律 2.是过滤的数量 去掉偶数就少一半 07/06 15:01
13F：→ peacedove:用个arraylist就可以解决质数本身没规律的问题啦 07/06 15:17
14F：→ peacedove:相关的演算法讨论 之前板上就有讨论过了 07/06 15:19