プログラミングのお題スレ Part22

**848** · 2025/09/15(月) 00:34:43.20

>>845 ruby
https://ideone.com/3I72I6
・キャッシュ探りながら構築
・c[桁の合計][幅] = とりうるパターン

**851** · 2025/09/15(月) 00:58:49.72

https://ideone.com/GWbQAx
・動きは >>851 といっしょ
・若干の整理

**デフォルトの名無しさん** · 2025/09/15(月) 22:27:44.05

>>850では行末に無駄な半角空白文字が出力される。消すには最後から3行目のnthPartition(m, n)を
trim( )で囲めば良い。

**852** · 2025/09/16(火) 01:02:30.84

>>845 ruby
https://ideone.com/n5Jqm3
・動きは >>851 といっしょ
・数値の内部表現を配列から整数へ変更

**854** · 2025/09/17(水) 22:30:29.22

>>845 ruby 2.5.5
https://ideone.com/oAQimi
・とりうるパターン数に着目し迫る
・tallyは2.7以降

**デフォルトの名無しさん** · 2025/09/17(水) 22:43:48.03

>>845
C++
https://ideone.com/I6K1tl

行列Aの計算で加減算・代入回数を>>849より減らした。実行時間の違いは分からなかった。

**デフォルトの名無しさん** · 2025/09/17(水) 23:39:47.32

>>856
BigInt化してm = 2000, n = 2¹⁰²⁴で実行したら違いが明確になった。

(1) >>849のBigInt版
https://ideone.com/S92L9G
(2) >>856のBigInt版
https://ideone.com/3x03xT

加減算・代入回数を削減した(2)の方が確かに速く、(1)の約4分の3の実行時間。

**855** · 2025/09/18(木) 21:13:33.56

>>845 ruby 2.5.5
https://ideone.com/Zm2433
・揃ってからcumsum、のリズムを廃止

**858** · 2025/09/19(金) 21:59:08.62

>>845 ruby 2.5.5
https://ideone.com/iwQNCH
・若干の整理（loop廃止、fill三回へ置き換え）

**859** · 2025/09/20(土) 21:39:31.29

>>845 ruby 2.5.5
https://ideone.com/jHqv2L
・内部表現の変更
　112225→[2,3,0,0,1]

**860** · 2025/09/22(月) 21:37:36.11

>>845 ruby 2.5.5
https://ideone.com/MDHX6v
・内部表現のさらなる変更
・パターン数を直接キャッシュするようにした
　cc[合計][幅] = とりうるパターン数

>>845 ruby
https://ideone.com/PB8S7w
・m = 2000, n = 1 << 1024

**861** · 2025/09/23(火) 01:13:48.01

>>845 c++
https://ideone.com/oma0Jf
・ruby版861の移植
・m = 2000, n = 1 << 1024

**862** · 2025/09/26(金) 21:58:13.14

>>845 ruby
https://ideone.com/YEGl7C
・実りの無い再帰を省略
・結果を配列で集めず整数で集める

>>845 c++
https://ideone.com/f62fkG
・rubyの移植版

>>845 ocaml
https://ideone.com/cHYmdv
・rubyの移植版
・任意精度整数は昔ながらのnumのBig_int使用
・ZarithのZは確かに速かったけどideoneでは使えずボツ

**デフォルトの名無しさん** · 2025/10/19(日) 18:23:02.12

お題
硬貨の種類と金額が与えられます。
硬化の合計がちょうど金額と同じになるように硬貨を選ぶとき、使用枚数の最小値を求めてください。
支払いが不可能なときは-1を出力します。
各硬貨は無制限に使用できます。
額面の大きい硬貨を優先して選ぶ貪欲法が常に最適解を与えるとは限らないことに注意。

入力
硬貨：[1,7,10]
金額：14

出力
使用枚数：2

**デフォルトの名無しさん** · 2025/10/19(日) 21:36:07.90

>>864
R
https://ideone.com/bUDu3l

**デフォルトの名無しさん** · 2025/10/22(水) 21:34:32.83

>>864
金額が大きい場合でも高速に求められるようにした。

R
https://ideone.com/NC6lV7
C++
https://ideone.com/52TbeF

**デフォルトの名無しさん** · 2025/10/26(日) 09:31:44.23

お題というか、協力してほしい感じなんですが、素因数分解関数を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

**デフォルトの名無しさん** · 2025/10/26(日) 09:50:23.90

あ、ただの素数判定でも良いです。
ちなみに、66..61の場合は6661までは素数ですが66661は素数じゃなくなりました。
なので、33..31もどこかで素数じゃなくなるのか？それともずっと素数になりそうなのか？って疑問が持ち上がりました。

**デフォルトの名無しさん** · 2025/10/26(日) 10:13:01.91

>>867
興を削いですまんが、「33...331は素数か」でググったら、AIが（あまり大きくない桁数で）答えを示してくれた…

**デフォルトの名無しさん** · 2025/10/26(日) 10:19:15.38

near-repdigit素数とかで研究されてるらしい

結果だけ知りたいなら↓がまとめてる
https://stdkmd.net/nrr/3/33331.htm

**869** · 2025/10/26(日) 10:21:11.68

>>869
ちなみに、以下の思考経路だったのでプログラミング的な思考がゼロだった訳では無い。
1.多倍長整数で組むべきかな？
2.でも64bit整数の範囲で合成数だったら馬鹿馬鹿しいな
3.組む前にカンニングしちゃえ
4.>>869

**デフォルトの名無しさん** · 2025/10/26(日) 17:08:32.87

>>869-871
いえいえ、ああ、やっぱりずっと素数という訳にはいかないんですね…。
何か素数の秘密に触れるヒントか？と心躍ったけど、そんな訳なかったですね(´・ω・｀)

あやうく数学スレで鼻息荒く書き込むところでした。

ありがとうございました<(_ _)>

**デフォルトの名無しさん** · 2025/10/26(日) 17:55:12.41

29bitで収まる範囲内
333333331 = 17 × 19607843
これを求められなかったHaskellはすごく遅い？

**デフォルトの名無しさん** · 2025/10/26(日) 23:06:07.50

>>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 なので、素数比較回数が多いのかと。

**デフォルトの名無しさん** · 2025/10/26(日) 23:07:37.04

あ、f の方を忘れた。
f のコードは変更なしです。

**デフォルトの名無しさん** · 2025/11/07(金) 05:48:17.42

>>868
cだとこんな感じでいいのかな？
3333333333333331くらいまで一瞬でできる

#include <stdio.h>

int main(void) {
long long d, n;

printf("Enter a number: ");
scanf("%lld", &n);

for (d = 2; d * d <= n; d++) {
if (n % d == 0)
break;
}
if (d * d <= n)
printf("%lld is divisible by %lld\n", n, d);
else
printf("%lld is prime.\n", n);

return 0;
}