質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

解決済

3回答

1936閲覧

素数判定に使われていると思われるアルゴリズム?が何なのか知りたい

opyon

総合スコア1009

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

0グッド

1クリップ

投稿2018/10/07 02:09

####知りたいこと
自分では全く思いつかなかったこのアルゴリズム?ぽいものが何なのか分かりません。
例えば◯◯の法則だよなど名前があるものだと調べてみたいと思います。
この法則が何かご存知の方いらっしゃればご教示ください。

####試したこと
ProjectEuler Problem10 Summation of primes
上記素数判定の問題をPythonで書くとプログラムが遅かったのであれこれ試行錯誤していました。
以前javaでは0.2秒程で動いていたコードを引っ張り出してPythonに書き直したり別の方法を試したりして約9秒掛かっていたものを3秒切れるくらいにまでは改善出来たのですがそれ以上は速くなりません。
Pythonって遅いらしいとも聞くしこんなものなのかなと思いつつ・・・

ネットからヒントを得ようと探していると次のコードの中アルゴリズム?ぽいものを見つけました。
コピペして実際に動かすと僅か0.2秒程で200万以下の素数の和を出力したので驚きました。
アルゴリズム?凄い!

素数 2乗 等差 アルゴリズムなどで検索してみましたが見つけられませんでした。
(見逃してるかもしれませんが)

####アルゴリズム?
自分の言葉で解釈した法則?:素数の2乗に素数の2倍の公差を持つ等差数列を足したものは素数では無い?
(数学もアルゴリズムも素人なので用語の使い方など間違っていたらすみません)
例えば素数p=3とした時pp:33=9 p2:32=6 9+6=15, 9+12=21, 9+18=27, ...
9,15,21,27,...は素数では無い?

コード抜粋

python

1for i in range(p * p, below, p * 2): 2 sieve[i] = False

コード全体(コピペ+計測用の追記)

python

1below = 2000000 2def find_prime_numbers_below(below): 3 total = 2 4 sieve = [True] * below 5 for p in range(3, below, 2): 6 if sieve[p]: 7 total += p 8 for i in range(p * p, below, p * 2): 9 sieve[i] = False 10 11 return total 12 13#計測用に追記 14import timeit 15print(timeit.timeit(lambda: print(find_prime_numbers_below(below)), number = 1)) 16 17#出力結果 18#142913828922 19#0.200956025

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答3

0

ベストアンサー

投稿2018/10/07 02:13

swordone

総合スコア20649

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

opyon

2018/10/07 02:15

ありがとうございます! 早速調べてみます!
swordone

2018/10/07 02:22

検索ワード、「2乗」とか「等差」とか抜いて普通に検索すれば見つかるのに…
opyon

2018/10/07 02:33

ですよねぇ~^^;
guest

0

素数判定機
https://tools.m-bsys.com/calculators/prime_number.php
から、たどって行くといろいろな情報が得られます。

投稿2018/10/07 03:23

katoy

総合スコア22324

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

opyon

2018/10/07 05:36

ありがとうございます。
guest

0

factorコマンドのドキュメントソースです。

試しに200万までの素数の和を計算

bash

1$ time (seq 1 2000000|factor|awk '$0*=!$3{s+=$1}END{print s}') 2142913828923 3 4real 0m0.996s 5user 0m1.459s 6sys 0m0.071s

投稿2018/10/07 02:22

編集2018/10/07 02:47
hichon

総合スコア5737

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

opyon

2018/10/07 02:35

覗いてみましたが目が回りそうでした^^;
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問