Q&A
ありがとうございます。
現在 for文 と if文程度の基礎的な文法のみで 素数を小さいほうから2000番目を表示するプログラムを考えています。
アドバイス
お願いいたします。
a = 100000000000000000 j = [] for i in range(1,a+1): if a % i == 0: j.append(i) print(j[1999])
回答6件
0
ベストアンサー
まず現状何ができているか確認しましょう。
確認のために、変数aの値は手ごろなものにします。
Python
1a = 20 2j = [] 3for i in range(1,a+1): 4 5 if a % i == 0: 6 j.append(i) 7 8# print(j[1999]) 9print(j)
実行結果 Wandbox
[1, 2, 4, 5, 10, 20]
見てわかるように、現状『指定の数の約数を列挙する』コードが完成しています。
素数を求められるようにする
素数の約数は、1とその数自体ですから、リストjの長さが2であったら素数だと言えます。
判定には組み込み関数 len を利用します。
Python
1>>> lst = [1, 2, 3] 2>>> len(lst) 33 4>>> 5>>> lst = [3, 1, 4, 1, 5, 9, 2] 6>>> len(lst) 77
約数の個数が二個ちょうどであるか ⇔ 素数であるか
素数を列挙できるようにする
直前に完成した、『素数判定プログラム』を利用します。
Python
1for i in range(上限): 2 素数判定 3 4 もし素数なら: 5 リストに追加
以上で完成です。
追記： nobitaさんが完成させたプログラム
Python
1a = 0 2b = 1 3q = [] 4w = [] 5i = 0 6 7 8for aa in range(1,100): 9 j = 0 10 for i in range(1,100): 11 12 if aa % i == 0: 13 14 j += 1 15 if 2 < j: 16 print(f"{aa}は素数ではない") 17 else: 18 print(f"{aa}は素数である")
イケてない部分もありますが、しっかり動いてるのでまずは充分でしょう。
書いてみた
他の回答に対抗して、『ifとforだけ』縛りを無視して書いてみた。
Python
1import itertools 2 3 4def is_prime(num, prime_list): 5 return all(num % prime != 0 for prime in prime_list) 6 7def gen_primes(): 8 prime_list = [2] 9 10 yield 2 11 for num in itertools.count(start=3, step=2): 12 if is_prime(num, prime_list): 13 prime_list.append(num) 14 yield num 15 16 17if __name__ == '__main__': 18 gen = gen_primes() 19 20 for _ in range(1999): 21 next(gen) 22 23 print( 24 next(gen) 25 )
投稿2018/09/05 11:24
編集2018/09/05 17:21
総合スコア35660
0
https://ja.m.wikipedia.org/wiki/エラトステネスの篩
普通はこういうのを使います。
for文とif文で書けますよ。
参考程度に。本当にあってるかな…
python
1ps = [2] 2 3def is_prime_countup(num, ps): 4 for p in ps: 5 if num % p == 0: 6 return False 7 return True 8 9i = 3 10while len(ps) < 2000: 11 if is_prime_countup(i, ps): 12 ps.append(i) 13 i += 1 14 15print(ps) 16print(len(ps))
気持ち高速化してみる。
python
1from math import sqrt 2ps = [2] 3 4def is_not_prime_countup(num, ps): 5 l = sqrt(num) 6 return any(num % p == 0 for p in ps if p <= l) 7 8i = 3 9while True: 10 if not is_not_prime_countup(i, ps): 11 ps.append(i) 12 if len(ps) == 5000: 13 break 14 i += 1 15 16print(ps) 17print(len(ps))
いろいろと悲しみしかなかったといっておく…
python
1import time 2from math import sqrt 3 4def timer(func): 5 def itimer(*args, **kwargs): 6 st = time.time() 7 ret = func(*args, **kwargs) 8 print(time.time() - st) 9 return ret 10 return itimer 11 12N = 10000 13 14@timer 15def f(): 16 ps = [2] 17 18 def is_prime_countup(num, ps): 19 l = sqrt(num) 20 for p in ps: 21 if num % p == 0: 22 return False 23 if p > l: 24 return True 25 return True 26 27 i = 3 28 while len(ps) < N: 29 if is_prime_countup(i, ps): 30 ps.append(i) 31 i += 1 32 33 return ps 34 35@timer 36def g(): 37 ps = [2] 38 39 def is_not_prime_countup(num, ps): 40 l = sqrt(num) 41 return any(num % p == 0 for p in ps if p <= l) 42 43 i = 3 44 while True: 45 if not is_not_prime_countup(i, ps): 46 ps.append(i) 47 if len(ps) == N: 48 break 49 i += 1 50 51 return ps 52 53ansf = f() 54ansg = g() 55assert all(i == j for i, j in zip(ansf, ansg))
投稿2018/09/05 12:22
編集2018/09/05 14:45
総合スコア8560
0
(i)素数かどうか判定する関数を作ります。
素数ならTrue, そうでないならFalseを返すようにしましょう。
(ii)while文で条件を満たすまでループさせて答えを求めます。
python
1import math 2 3def is_prime(n): 4 if n == 1: return False 5 6 for k in range(2, int(math.sqrt(n)) + 1): 7 if n % k == 0: 8 return False 9 10 return True 11 12count = 0 13num = 1 14 15while count < 2000: 16 17 num += 1 18 if is_prime(num): 19 count += 1; 20 21print(num)
投稿2018/09/05 11:39
退会済みユーザー
総合スコア0
0
参考情報
- Pythonで素数の効率的な無限のジェネレータを実装するには？
https://code.i-harness.com/ja/q/21c096
- Finding nth Prime using Python and Sieve of Eratosthenes
https://codereview.stackexchange.com/questions/185219/
- Calculating the Nth prime number
https://www.codeproject.com/Articles/1228398/Calculating-the-Nth-prime-number
Finding nth Prime using Python and Sieve of Eratosthenes のページの中のコードの一つを
実際に試してみます。2000 編目でなく 20000 番目を求めてみました。
python3
1def gen_primes(): 2 D = {} 3 q = 2 # first integer to test for primality. 4 5 while True: 6 if q not in D: 7 # not marked composite, must be prime 8 yield q 9 10 # first multiple of q not already marked 11 D[q * q] = [q] 12 else: 13 for p in D[q]: 14 D.setdefault(p + q, []).append(p) 15 # no longer need D[q], free memory 16 del D[q] 17 18 q += 1 19 20primes = gen_primes() 21 22# for p in primes: 23# print(p) 24 25for _ in range(19999): 26 next(primes) 27 28print(next(primes))
実行例：
i病以下で処理できています。
投稿2018/09/05 14:03
編集2018/09/06 17:07
総合スコア22324
0
素数の計算とのことですが、2000番目を求めるということなのでそのまま演算を行うと、処理時間が膨大になってしまう可能性があります。
まずは、求め方のアルゴリズムから考えたほうが良いでしょう。
素数を求める方法として有名なのは
- エラトステネスの篩を適用したもの
- フェルマーの小定理を用いるもの
（こちらは素数でない数(擬素数)を素数であると判断することがありますので、今回のご質問には不適切ですが）
などがあります。
また、上記を用いずとも、素数ではない数（合成数といいます）の以下の特徴を利用すると高速に処理が行えます。
ある合成数nは、2～√nまでの範囲に1つ以上の約数を持つ
例として21という数は、2～√21(≒4.58)までの範囲である3という約数を持つため合成数であるということです。
これは、21の約数として3を見つけることは、同時に対となる数7が存在することを見つけていることになるのです。
さて、これをpythonのコードで表現すると以下のようになります。
python
1p = [] 2limit = 100 3 4for k in range(2, limit+1): 5 factor = 0 6 7 # 繰り返しの上限を対象の平方根にする 8 for div in range(2, math.floor(math.sqrt(k))+1): 9 if k % div == 0: 10 factor += 1 11 12 # 範囲内の約数が無ければ素数である 13 if factor == 0: 14 p.append(k) 15
あとはこれに2000番目の値を表示する部分を加えれば目的を満たせると思います。
投稿2018/09/05 13:40
編集2018/09/05 13:48
総合スコア118
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2018/09/05 11:39
2018/09/05 11:40
2018/09/05 12:01
2018/09/05 12:04
2018/09/05 12:16
2018/09/05 12:17
2018/09/05 12:28
2018/09/05 12:54
2018/09/05 12:54
2018/09/05 12:55
2018/09/05 12:58
2018/09/05 13:11
2018/09/05 13:11
2018/09/05 13:16
2018/09/05 13:26
2018/09/05 13:55
2018/09/05 13:56
2018/09/05 14:00 編集
2018/09/05 14:13
2018/09/05 14:13
2018/09/05 14:18
2018/09/05 14:31
2018/09/05 14:36 編集
2018/09/05 14:39
2018/09/05 14:39
2018/09/05 14:43
2018/09/05 14:50
2018/09/05 14:59 編集
2018/09/05 15:00
2018/09/05 15:01
2018/09/05 15:09
2018/09/05 22:14