project Euler 7問目

Share This:

今回は、Project Euler の 7 問目の解き方を紹介します。
問題文は、次のようになっております。

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10 001st prime number?

「10001 番目の素数を見つけよ!」という問題です。この問題を解くためには、素数の効率的な探し方を知っている必要があります。

素数は、「自然数で、正の約数が 1 と自分自身のみであるもの」です。

このことより、ある数字 n に対して 2 から n-1 までの数字で割り、割り切れない数字を探せば良いと考えられます。しかし、この方法ではメモリーオーバーで止まります。そこで、エラトステネスの篩を使います。

以下、参考例です。C++ で書きました。

素数は絶対に奇数であるため n = 3 から開始し、その後 2 ずつ増やすようにしています (n += 2) 。また、k<=sqrt(n) としています。

こういった問題を解くことは、計算化学に直接は関係ありません。しかし、より効率的な探索方法を見つける、簡単なプログラムを自作できるようになっておく(洗練されたコードである必要はない)、初歩的な数学の知識を身につけておくといったことは、計算化学を行っていく上で重要です。

Gauss View で log ファイルを視覚化すると化合物を扱っている感覚になりますが、log ファイルの中身は数字です。どのようにしたら大量の数字を効率的に処理できるかを常に考えることが計算化学では重要だと思います。

コメントを残す(投稿者名のみ必須)