問題(和訳)

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

回答例

$ time seq 100 | factor | awk 'NF==2{print $2}' | awk 'BEGIN{a=1}{a*=$1;print $1,a}' | awk '$2<1000000'
2 2
3 6
5 30
7 210
11 2310
13 30030
17 510510
 
real    0m0.012s
user    0m0.006s
sys     0m0.012s

解説

n/phy(n) が大きい
= phy(n)が小さい
= nは「互いに素ではない数」が多い
= nは素因数分解すると、小さい因数の種類が多い

 例:nが偶数だった場合、n以下の偶数は「互いに素ではない」

= 素数を小さい方から掛け合わせていき、1,000,000以下の最も大きい数を求めれば良い

 # 素数を抽出
 seq 100 | factor | awk 'NF==2{print $2}' | 
 
 # 素数を小さい方から掛け合わせる
 awk 'BEGIN{a=1}{a*=$1;print $1,a}' | 
 
 # 1,000,000 以下を抽出
 awk '$2<=1000000'

備考

条件を満たすn/phy(n)を求める方法

 seq 100 |
 factor |
 awk 'NF==2{print $2}' |
 awk 'BEGIN{a=1}{a*=$1;print $1,a}' |
 awk '$2<1000000' ;)|
 awk '{a=a" "$1;n=$2}END{print n,a}'|
 awk '{for(i=2;i<=NF;i++){b=$i;while(b<$1){a[b];b+=$i}};print $1,$1-length(a)-1}' |
 awk '{print $0,$1/$2}'

力技で求める(やめとけ!)

 seq 1000000 | factor | 
 grep -w 2 | grep -w 3 | grep -w 5 | grep -w 7 | grep -w 11 | grep -w 13 | grep -w 17 | 
 awk '{sub(":","",$1);for(i=2;i<=NF;i++){print $1,$i}}'| 
 uniq -c | 
 awk 'a!=$2{print a,b;a=$2;b=""}{b=b" "$3}END{print a,b}' | 
 awk '{delete a;for(i=2;i<=NF;i++){b=$i;while(b<$1){a[b];b+=$i}};print $1,$1-length(a)-1}' | 
 sed 1d | 
 awk '{print $0,$1/$2}' | 
 sort -sk3,3nr | 
 head

トップ   編集 凍結 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2019-03-24 (日) 07:44:02