プログラミングのお題スレ Part22 (876ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
867(2): 10/26(日)09:31 ID:Y3+SSpql(1/5)調 AAS
お題というか、協力してほしい感じなんですが、素因数分解関数をHaskellで書いて色んな数を素因数分解して遊んでいたら確認したい事実に出くわしたので。
31 <- 素数
331 <- 素数
3331 <- 素数
33331 <- 素数
333331 <- 素数
と、３が５個並んで末尾が１の数字までは素数という事が分かりましたが、いかんせん、ノートだと力不足。
それにCとかで書き直したらもっと先まで行けるかも？という事で、この先、どこまで33...31が素数なのかを調べて欲しいのです。
協力お願いします<(_ _)>
一応、Haskellではこんなコードです。
factorization n = f primes n
where primes = 2:(sieve [3,5..])
where sieve (p:xs) = p:(sieve [x | x <- xs, x `mod` p /= 0])
f (p:ps) n | n <= p = [n]
f (p:ps) n | n `mod` p == 0 = p:f (p:ps) (n `div` p)
f (p:ps) n = f ps n
868(1): 10/26(日)09:50 ID:Y3+SSpql(2/5)調 AAS
あ、ただの素数判定でも良いです。
ちなみに、66..61の場合は6661までは素数ですが66661は素数じゃなくなりました。
なので、33..31もどこかで素数じゃなくなるのか？それともずっと素数になりそうなのか？って疑問が持ち上がりました。
872: 10/26(日)17:08 ID:Y3+SSpql(3/5)調 AAS
>>869-871
いえいえ、ああ、やっぱりずっと素数という訳にはいかないんですね…。
何か素数の秘密に触れるヒントか？と心躍ったけど、そんな訳なかったですね(´・ω・｀)
あやうく数学スレで鼻息荒く書き込むところでした。
ありがとうございました<(_ _)>
874: 10/26(日)23:06 ID:Y3+SSpql(4/5)調 AAS
>>873
速いアルゴリズムに変えたら何とか1分ほどでその数字まで届きました。
（そもそも、>867 のは美しいとか短いとかの枕詞が付くコードですし。33...31に気付かなかったら4桁ぐらいが実用的ならおｋだったので）
改良版Haskell
pfactorization = f primes
where primes =2:3:5#primes
where n#x@(m:q:y)=[n|gcd m n<2]++(n+2)#last(x:[m*q:y|q^2-3<n])
というか、それより1桁少ない方が少し時間かかりますね。
19607843 < 33333331 なので、素数比較回数が多いのかと。
875: 10/26(日)23:07 ID:Y3+SSpql(5/5)調 AAS
あ、f の方を忘れた。
f のコードは変更なしです。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.025s