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