2008/07/03

求質數

今天用找質數問題來練習 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 時解密的困難度,而找到超大的質數表示你你努力、很聰明,大家會對你無比的尊敬,還給你一筆很大的獎金

5 則留言:

  1. 6n+1 // 判斷
    6n+2 // 2(3n+1)
    6n+3 // 3(2n+1)
    6n+4 // 2(3n+2)
    6n+5 // 判斷

    觀察法得證XD

    回覆刪除
  2. 發現我沒有被點名,所以我不該證明XDXD

    回覆刪除
  3. 我以前用Sieve跑Java的質數表
    長度20000000跑了4.x秒
    還可以接受啦

    PS:最佳化過的C++用不到1秒...囧

    回覆刪除
  4. 二千萬不夠大啦,Google 的題目是十位數字耶!

    回覆刪除
  5. when k>0,where k is an integer,
    6k
    6k+1
    6k+2=2(3k+1)
    6k+3=3(2k+1)
    6k+4=2(3k+2)
    6k+5
    6k+6=6(k+1)
    6k+7=6(k+1)+1
    ...

    回覆刪除