sh/Problem 50

問題（和訳）†

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2050

回答例†

[nobuoki@4b22771af61a projecteuler][master *]$ time seq 1000000 | factor | awk 'NF==2' | sed 's/.* //' | awk '{a[NR]=$1;b[$1]++}END{for(i=NR;i>=1;i--){s=0;c="";for(j=i;j>=1;j--){if((s+a[j])>1000000){break};s+=a[j];c=c" "a[j];if(b[s]){print s,c}}}}' | awk 'NF>21{print $1,NF-1}' | LANG=C sort -sk2,2n | sed -n '$p'
997651 543

real 0m2.056s
user 0m2.691s
sys 0m0.180s
[nobuoki@4b22771af61a projecteuler][master *]$

↑

解説†

 # 素数のリストを作成
 seq 1000000 | factor | awk 'NF==2' | sed 's/.* //' | 
 
 # 連続する素数の合計値が素数になるものを探す
 awk '
 
 # 素数の大きさ順リスト(a)と、素数をキーにしたリスト(b)を作成
 {a[NR]=$1;b[$1]++}
 
 END{
        # 素数を大きな方から順に足すための準備(s:和の合計値, c:素数列)
        for(i=NR;i>=1;i--){
                s=0;
                c="";
 
                # j番目に大きな素数から順に足す
                for(j=i;j>=1;j--){
 
                        # 1,000,000 を超えたらループ脱出
                        if((s+a[j])>1000000){
                                break
                        };
                        s+=a[j];
                        c=c" "a[j];
 
                        # 合計値が素数だったら出力
                        if(b[s]){
                                print s,c
                        }
                }
        }
 }' | 
 
 # 21個以上の連続する素数の合計値のみ抽出
 awk 'NF>21{print $1,NF-1}' | 
 
 # 連続する素数の数の順に並べ替え
 LANG=C sort -sk2,2n | 
 
 # 最大の連続数を表示（答えが1つだと分かっているので最終行のみ表示）
 sed -n '$p'

問題（和訳）†

回答例†

解説†

Menu

最新の20件

古のコンテンツ