いくつかの問題があります:
continue次のループ反復に移動します - しかし、あなたは本当にそれを停止したいですbreakこれは、いくつかの修正を加えたコードです。素数のみを出力します。
import math
def main():
count = 3
while True:
isprime = True
for x in range(2, int(math.sqrt(count) + 1)):
if count % x == 0:
isprime = False
break
if isprime:
print count
count += 1
より効率的な素数生成については、他の人が示唆しているように、エラトステネスのふるいを参照してください。これは、多くのコメントを含む、最適化された優れた実装です。
# Sieve of Eratosthenes
# Code by David Eppstein, UC Irvine, 28 Feb 2002
# http://code.activestate.com/recipes/117119/
def gen_primes():
""" Generate an infinite sequence of prime numbers.
"""
# Maps composites to primes witnessing their compositeness.
# This is memory efficient, as the sieve is not "run forward"
# indefinitely, but only as long as required by the current
# number being tested.
#
D = {}
# The running integer that's checked for primeness
q = 2
while True:
if q not in D:
# q is a new prime.
# Yield it and mark its first multiple that isn't
# already marked in previous iterations
#
yield q
D[q * q] = [q]
else:
# q is composite. D[q] is the list of primes that
# divide it. Since we've reached q, we no longer
# need it in the map, but we'll mark the next
# multiples of its witnesses to prepare for larger
# numbers
#
for p in D[q]:
D.setdefault(p + q, []).append(p)
del D[q]
q += 1
ジェネレータを返すことに注意してください。
def is_prime(num):
"""Returns True if the number is prime
else False."""
if num == 0 or num == 1:
return False
for x in range(2, num):
if num % x == 0:
return False
else:
return True
>> filter(is_prime, range(1, 20))
[2, 3, 5, 7, 11, 13, 17, 19]
20までのすべての素数をリストに入れます。エラトステネスのふるいを使用することもできましたが、非常にシンプルなものが必要だとおっしゃいました。;）
print [x for x in range(2,100) if not [t for t in range(2,x) if not x%t]]
これが私が持っているものです：
def is_prime(num):
if num < 2: return False
elif num < 4: return True
elif not num % 2: return False
elif num < 9: return True
elif not num % 3: return False
else:
for n in range(5, int(math.sqrt(num) + 1), 6):
if not num % n:
return False
elif not num % (n + 2):
return False
return True
ある数の約数についてすでに素数をチェックするだけなので、大きな数の場合はかなり高速です。
これで、素数のリストを生成する場合は、次のことができます。
# primes up to 'max'
def primes_max(max):
yield 2
for n in range(3, max, 2):
if is_prime(n):
yield n
# the first 'count' primes
def primes_count(count):
counter = 0
num = 3
yield 2
while counter < count:
if is_prime(num):
yield num
counter += 1
num += 2
ここでジェネレーターを使用することは、効率のために望ましいかもしれません。
そして、参考のために、言う代わりに：
one = 1
while one == 1:
# do stuff
あなたは簡単に言うことができます：
while 1:
#do stuff
奇数のみを考慮した単純な最適化による別の単純な例。すべてが遅延ストリーム (python ジェネレーター) で行われます。
使い方: 素数 = リスト (create_prime_iterator(1, 30))
import math
import itertools
def create_prime_iterator(rfrom, rto):
"""Create iterator of prime numbers in range [rfrom, rto]"""
prefix = [2] if rfrom < 3 and rto > 1 else [] # include 2 if it is in range separately as it is a "weird" case of even prime
odd_rfrom = 3 if rfrom < 3 else make_odd(rfrom) # make rfrom an odd number so that we can skip all even nubers when searching for primes, also skip 1 as a non prime odd number.
odd_numbers = (num for num in xrange(odd_rfrom, rto + 1, 2))
prime_generator = (num for num in odd_numbers if not has_odd_divisor(num))
return itertools.chain(prefix, prime_generator)
def has_odd_divisor(num):
"""Test whether number is evenly divisable by odd divisor."""
maxDivisor = int(math.sqrt(num))
for divisor in xrange(3, maxDivisor + 1, 2):
if num % divisor == 0:
return True
return False
def make_odd(number):
"""Make number odd by adding one to it if it was even, otherwise return it unchanged"""
return number | 1
私の意見では、機能的なアプローチを取るのが常に最善です。
そのため、最初に数値が素数かどうかを調べる関数を作成し、必要に応じてループまたは他の場所で使用します。
def isprime(n):
for x in range(2,n):
if n%x == 0:
return False
return True
次に、単純なリスト内包表記またはジェネレータ式を実行して素数のリストを取得します。
[x for x in range(1,100) if isprime(x)]
トピックを調べて、スレッドで例を探して、私のバージョンを作成してみてください。
from collections import defaultdict
# from pprint import pprint
import re
def gen_primes(limit=None):
"""Sieve of Eratosthenes"""
not_prime = defaultdict(list)
num = 2
while limit is None or num <= limit:
if num in not_prime:
for prime in not_prime[num]:
not_prime[prime + num].append(prime)
del not_prime[num]
else: # Prime number
yield num
not_prime[num * num] = [num]
# It's amazing to debug it this way:
# pprint([num, dict(not_prime)], width=1)
# input()
num += 1
def is_prime(num):
"""Check if number is prime based on Sieve of Eratosthenes"""
return num > 1 and list(gen_primes(limit=num)).pop() == num
def oneliner_is_prime(num):
"""Simple check if number is prime"""
return num > 1 and not any([num % x == 0 for x in range(2, num)])
def regex_is_prime(num):
return re.compile(r'^1?$|^(11+)\1+$').match('1' * num) is None
def simple_is_prime(num):
"""Simple check if number is prime
More efficient than oneliner_is_prime as it breaks the loop
"""
for x in range(2, num):
if num % x == 0:
return False
return num > 1
def simple_gen_primes(limit=None):
"""Prime number generator based on simple gen"""
num = 2
while limit is None or num <= limit:
if simple_is_prime(num):
yield num
num += 1
if __name__ == "__main__":
less1000primes = list(gen_primes(limit=1000))
assert less1000primes == list(simple_gen_primes(limit=1000))
for num in range(1000):
assert (
(num in less1000primes)
== is_prime(num)
== oneliner_is_prime(num)
== regex_is_prime(num)
== simple_is_prime(num)
)
print("Primes less than 1000:")
print(less1000primes)
from timeit import timeit
print("\nTimeit:")
print(
"gen_primes:",
timeit(
"list(gen_primes(limit=1000))",
setup="from __main__ import gen_primes",
number=1000,
),
)
print(
"simple_gen_primes:",
timeit(
"list(simple_gen_primes(limit=1000))",
setup="from __main__ import simple_gen_primes",
number=1000,
),
)
print(
"is_prime:",
timeit(
"[is_prime(num) for num in range(2, 1000)]",
setup="from __main__ import is_prime",
number=100,
),
)
print(
"oneliner_is_prime:",
timeit(
"[oneliner_is_prime(num) for num in range(2, 1000)]",
setup="from __main__ import oneliner_is_prime",
number=100,
),
)
print(
"regex_is_prime:",
timeit(
"[regex_is_prime(num) for num in range(2, 1000)]",
setup="from __main__ import regex_is_prime",
number=100,
),
)
print(
"simple_is_prime:",
timeit(
"[simple_is_prime(num) for num in range(2, 1000)]",
setup="from __main__ import simple_is_prime",
number=100,
),
)
このコードを実行した結果は、興味深い結果を示しています。
$ python prime_time.py
Primes less than 1000:
[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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
Timeit:
gen_primes: 0.6738066330144648
simple_gen_primes: 4.738092333020177
is_prime: 31.83770858097705
oneliner_is_prime: 3.3708438930043485
regex_is_prime: 8.692703998007346
simple_is_prime: 0.4686249239894096
ここで、さまざまな質問に対して正しい答えがあることがわかります。素数ジェネレーターgen_primesは正しい答えのように見えます。しかし、素数チェックの場合は、このsimple_is_prime関数の方が適しています。
これはうまくいきますが、機能させるためのより良い方法に対して常にオープンですis_prime。
これは宿題のようですので、詳細な説明ではなくヒントを示します。私が間違っていると思ったら訂正してください。
除数が均等になっているのを見ると、ベイルアウトするまではうまくいっています。
しかし、分割されていない数値が1つでも表示されるとすぐに、「カウント」を出力します。たとえば、2は9に均等に分割されません。しかし、それは9を素数にしません。範囲内の番号が一致しないことが確実になるまで、続行することをお勧めします。
（他の人が答えたように、Sieveははるかに効率的な方法です...この特定のコードがあなたが望むことをしていない理由を理解するのを助けることを試みているだけです）
考えられるすべての除数が、チェックしている数を均等に除算しないようにする必要があります。この場合、可能な除数の1つだけが数値を均等に除算しないときはいつでも、チェックしている数値を出力します。
また、continueステートメントを使用する必要はありません。これは、数値が素数ではないことがすでにわかっている場合に、continueによって次の可能な除数がチェックされるためです。
import time
maxnum=input("You want the prime number of 1 through....")
n=2
prime=[]
start=time.time()
while n<=maxnum:
d=2.0
pr=True
cntr=0
while d<n**.5:
if n%d==0:
pr=False
else:
break
d=d+1
if cntr==0:
prime.append(n)
#print n
n=n+1
print "Total time:",time.time()-start
素数を直接計算したい場合は、次のようにします。
def oprime(n):
counter = 0
b = 1
if n == 1:
print 2
while counter < n-1:
b = b + 2
for a in range(2,b):
if b % a == 0:
break
else:
counter = counter + 1
if counter == n-1:
print b
範囲内のすべての素数を見つけたい場合は、次のようにすることができます。
def is_prime(num):
"""Returns True if the number is prime
else False."""
if num == 0 or num == 1:
return False
for x in range(2, num):
if num % x == 0:
return False
else:
return True
num = 0
itr = 0
tot = ''
while itr <= 100:
itr = itr + 1
num = num + 1
if is_prime(num) == True:
print(num)
tot = tot + ' ' + str(num)
print(tot)
while its <=と範囲の番号を追加するだけです。
出力：
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 101
continue ステートメントが間違っているようです。
2 は最初の素数なので、2 から始めます。
「while True:」と書くと無限ループになります。
def genPrimes():
primes = [] # primes generated so far
last = 1 # last number tried
while True:
last += 1
for p in primes:
if last % p == 0:
break
else:
primes.append(last)
yield last
def check_prime(x):
if (x < 2):
return 0
elif (x == 2):
return 1
t = range(x)
for i in t[2:]:
if (x % i == 0):
return 0
return 1