193. Squarefree Numbers

　久しぶりにProjectEulerをやる。ProjectEulerはオンラインジャッジシステムで、数論の問題が中心となっている。UVa,PKUなどと異なりソースコードを送るのでなく、答えのみ送る。計算はローカルでやるのでマシンパワーがあれば有利だけど、１分ルールというのがあって、アルゴリズムさえ適切なら普通のノートパソコンでも１分以下ぐらいで解けるようになっている。今日は次の問題を考えた。

http://projecteuler.net/index.php?section=problems&id=193
　NがSquarefree Numberとは、N|p^2を満たす素数pが存在しない数である。2^50以下のSquarefree Numberがいくつあるか？という問題。

　まずシンプルな解より考えた。単一の数NをSquarefreeか否かを判定する簡単の方法はroot(N)までの素数で試し割。計算量O(root(N))。それを2^50。まあ、実装するまでもなく無理ですね。次に深く考え始める前にSquarefree Numberについて調べる。たまに一歩進んだ知識が要求される問題があるので。特になかった。次に考えた事は次のどっちをいくか。

1. 2^50以下のSquarefree Numberを数える
2. 2^50以下の非Squarefree Numberを数える。それを2^50から引く。

1.の方法がないのはすぐに分かった。素数は必ずSquarefreeになるので、2^50以下の素数は全て数える必要性が出てくる。これは数分そこそこでは無理である。正確な値が求められてるので素数定理は使えない。なので2.の方法で数える。