EKG Sequence (ZOJ Problem Set - 1801)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1801

問題

EKG Sequenceという数列がある。この数列の初項は1、2項目は2である。m項目はm-1項目と共通の素因数を持つ数値でまだ数列に出現していない最小の数値である。数値nは何項目に出現するか求めよ。
1<=n<=300000
答えは1000000以下になる。

解法

100万項目まで全て順番に求めておけば良い。てきとうにやるとMLEとかTLEとか食らうので、篩をする時に割られる数値を覚えて置けば素因数分解は高速化できる。数列に出現してない最小の数値を高速に求めるには各素数がどこまで見たかを記憶しておけば良い。