【iOS版アプリ】不具合のお知らせ

本で、2^67-1 を手計算で因数分解するのに、日曜日が3年かかるという話があったのですが、
・手計算でできるのでしょうか?
・逆に手計算で3年もかかるものでしょうか?
どうやって計算したと思いますか?

A 回答 (1件)

ある自然数を素因数分解する方法として誰もが思いつくのは


その数を割り切る素数を探すということです.
2^67-1の素因数分解は
193707721×761838257287
です.
193707721(9桁)は10749692番目の素数,
761838257287(12桁)は28947792875番目の素数です.
素数の一覧表を見るのが禁止だとすると,これらが素数であることを確かめる必要があります.
ちなみに,レオンハルト・オイラーが生涯に発見した最大の素数は多分
2147483647(10桁)です.

2^n-1という形をした数をメルセンヌ数といい,それが素数であるときメルセンヌ素数といいます.
Wikipedia「メルセンヌ数」によれば
素数pに対し2^p-1の素因数は2pを法として1と合同,8を法として1または-1と合同だそうです.67は素数なのでこれが使えます.

【メルセンヌ素数の歴史(Wikipediaより抜粋)】
1772年 オイラーが8番目のメルセンヌ素数2^13-1=2147483647を発見
1876年 リュカが12番目のメルセンヌ素数2^127-1を発見
1996年 メルセンヌ素数の発見を目的としてGIMPSが発足
現在までに51個のメルセンヌ素数が発見されており,そのうち順番が確定しているのは47個
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています


このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング