求質數

今天用找質數問題來練習 Java，並且把質數範圍定到十位數之上，逼自己學 BigDecimal，順便看看 Java 可以跑多快。

Java 在四位數執行速度還蠻快的，至少沒有讓我等到睡著，但是後面就沒有那麼輕鬆了。後來想到小學習題有提到質數和「6」的關係，不過不知道為什麼國中之後就完全沒有蛛絲馬跡，乾脆拿出來跑一次看看這個理論是不是真的。

以下是 1 到 100 的質數：

1 = 6 * 0 + 1
2
3
5 = 6 * 1 – 1
7 = 6 * 1 + 1
11 = 6 * 2 – 1
13 = 6 * 2 + 1
17 = 6 * 3 – 1
19 = 6 * 3 + 1
23 = 6 * 4 – 1
29 = 6 * 5 – 1
31 = 6 * 5 + 1
37 = 6 * 6 + 1
41 = 6 * 7 – 1
43 = 6 * 7 + 1
47 = 6 * 8 – 1
53 = 6 * 9 – 1
59 = 6 * 10 – 1
61 = 6 * 10 + 1
67 = 6 * 11 + 1
71 = 6 * 12 – 1
73 = 6 * 12 + 1
79 = 6 * 13 + 1
83 = 6 * 14 – 1
89 = 6 * 15 – 1
97 = 6 * 16 + 1

以目前的狀況來看，質數都是 6 的倍數加減 1。但是不知道往後這個理論是不是還能用，點名叫 legnaleurc 證明一下好了…. XD

另外在 PTT 上有找到幾個演算法，有興趣可以去寫寫看。

Sieve of Eratosthenes @ MathWorld
http://mathworld.wolfram.com/SieveofEratosthenes.html

Prime Sieve of Eratosthenes @ Algorithmist
http://www.algorithmist.com/index.php/Sieve

2008.07.03 補充：
挖到一篇文章，裡面提到「為什麼要找質數」，理由如下：

• 這是傳統……XD
• 附加價值
• 無上的榮耀
• 對電腦的考驗
• ……….

質數的附加價值很多，例如 RSA 加密演算法，就是利用超大質數相乘不容易因式分解，增加沒有 key 時解密的困難度，而找到超大的質數表示你你努力、很聰明，大家會對你無比的尊敬，還給你一筆很大的獎金。