2018-04-26

【Python】高速かつ簡単にNまでの素数を求めるプログラム【エラトステネスの篩】

Pythonの練習課題として，Nまでの素数を求めるプログラムを「エラトステネスの篩」というアルゴリズムを用いて実装しました．

エラトステネスの篩（ふるい）とは
プログラム

エラトステネスの篩（ふるい）とは

今回は，wikipediaの解説を元にプログラムを実装しました．
エラトステネスの篩 - Wikipedia

アルゴリズム
指定された整数x以下の全ての素数を発見するアルゴリズム。右のアニメーションでは以下のステップにそって2 から 120 までの数に含まれる素数をさがしている。
ステップ 1
探索リストに2からxまでの整数を昇順で入れる。
ステップ 2
探索リストの先頭の数を素数リストに移動し、その倍数を探索リストから篩い落とす。
ステップ 3
上記の篩い落とし操作を探索リストの先頭値がxの平方根に達するまで行う。
ステップ 4
探索リストに残った数を素数リストに移動して処理終了。

非常にシンプルなアルゴリズムで，個人的には速さよりも実装の簡単さの方が今回はありがたかったです．
エラトステネスの篩の速さについてはこちらのサイトがわかりやすく参考になりそうです．

プログラム

実際にPythonで実装したコードがこちらです．

実行結果

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

正直正しく実装できているかは不安ですが，100までの素数は正しく得られました．

2018-04-22

プログラムで解く数学の問題 -Project Eulerをやってみた-

Python プログラミング

最近学び始め，今後使う予定があるpythonの練習のために，以前に存在を知って気になっていた「Project Euler」に登録してみました．

Project Eulerとは
問題1
問題2

Project Eulerとは

Project Eulerは，プログラムで解く数学的な問題が掲載されているサイトです．
全て英語で書かれていますが，日本語に翻訳しているwikiも存在しています．
Project Euler - PukiWiki

実際に，アカウント登録をしてから問題を解く手順などは，こちらで詳しく解説されています．

実際に問題を2問だけ解いてみました．

問題1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.
Problem 1 - Project Euler

日本語訳

10未満の自然数のうち, 3 もしくは 5 の倍数になっているものは 3, 5, 6, 9 の4つがあり, これらの合計は 23 になる.

同じようにして, 1000 未満の 3 か 5 の倍数になっている数字の合計を求めよ. Problem 1 - PukiWiki

解くために書いたソースコード

i = 0
total = 0
for i in range(1000):
    if i % 3 == 0 or i % 5 == 0 :
        total += i
print(total)

実行結果

233168

問題2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Problem 2 - Project Euler

日本語訳

フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば, 最初の10項は以下の通りである.

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 数列の項の値が400万以下の, 偶数値の項の総和を求めよ.

Note:この問題は最近更新されました. お使いのパラメータが正しいかどうか確認してください.
Problem 2 - PukiWiki

解くために書いたソースコード

f = 0
pre = [1,2]
total = 2
while f < 4000001:
    f = pre[0] + pre[1]
    pre[0] = pre[1]
    pre[1] = f
    if f % 2 == 0 :
        total += f
print(total)