Einfache Prime Generator in Python
https://stackoverflow.com/questions/567222
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Könnte mir bitte jemand sagen, was ich mit diesem Code falsch machen werde? Es druckt nur ‚count‘ sowieso. Ich will nur einen sehr einfachen Prime-Generator (nichts Besonderes).
import math
def main():
count = 3
one = 1
while one == 1:
for x in range(2, int(math.sqrt(count) + 1)):
if count % x == 0:
continue
if count % x != 0:
print count
count += 1
Lösung
Es gibt einige Probleme:
- Warum drucken Sie aus Zählung, wenn es nicht durch x dividieren hat? Es bedeutet nicht, es ist Primzahl, es bedeutet nur, dass diese besondere x es nicht teilen
-
continuegeht in die nächste Schleife Iteration - aber Sie wirklich wollen, um es zu stoppenbreakmit
Hier ist der Code mit ein paar Korrekturen, es druckt nur Primzahlen:
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
Für viele effiziente prime Generation finden Sie im Sieb des Erastothenes, wie andere vorgeschlagen haben. Hier ist eine schöne, optimierte Implementierung mit vielen Kommentaren:
# 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
Beachten Sie, dass es einen Generator zurückgibt.
Andere Tipps
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]
Wir werden alle Primzahlen bis zu 20 in einer Liste bekommen. Ich hätte Sieb des Eratosthenes verwendet, aber sie sagte Sie wollen etwas, das ganz einfach. ;)
print [x for x in range(2,100) if not [t for t in range(2,x) if not x%t]]
re ist mächtig:
import re
def isprime(n):
return re.compile(r'^1?$|^(11+)\1+$').match('1' * n) is None
print [x for x in range(100) if isprime(x)]
###########Output#############
[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]
def primes(n): # simple Sieve of Eratosthenes
odds = range(3, n+1, 2)
sieve = set(sum([range(q*q, n+1, q+q) for q in odds],[]))
return [2] + [p for p in odds if p not in sieve]
>>> primes(50)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
Um zu testen, ob eine Zahl prim ist:
>>> 541 in primes(541)
True
>>> 543 in primes(543)
False
Hier ist eine einfach (Python 2.6.2) Lösung ..., die mit dem OP ursprünglichen Anfrage (jetzt sechs Monate alt) online ist; und sollte eine durchaus akzeptable Lösung in jeder sein „Programmierung 101“ Natürlich ... also diesen Beitrag.
import math
def isPrime(n):
for i in range(2, int(math.sqrt(n)+1)):
if n % i == 0:
return False;
return n>1;
print 2
for n in range(3, 50):
if isPrime(n):
print n
Diese einfache „Brute-Force-Methode“ ist „schnell genug“ für die Zahlen bis zu etwa 16.000 auf moderne PCs (dauerte ca. 8 Sekunden auf meinem 2GHz Kasten).
Offensichtlich ist dies effizient viel mehr getan werden könnte, indem sie nicht die primeness jeder geraden Zahl neu zu berechnen, oder jedes Vielfaches von 3, 5, 7, usw. für jede einzelne Zahl ... Siehe Sieb des Eratosthenes oder sogar die Sieb des Atkin wenn Sie das Gefühl besonders mutig und / oder verrückt.
Gewährleistungsausschluß: Ich bin ein Python-Noob. Bitte nehmen Sie nicht alles, was ich sagen als Evangelium.
Zu meiner Meinung nach ist es immer am besten, den funktionalen Ansatz,
So ich eine Funktion zuerst herausfinden, ob die Zahl eine Primzahl ist oder nicht, dann verwenden Sie es in Schleife oder einer anderen Stelle als notwendig.
def isprime(n):
for x in range(2,n):
if n%x == 0:
return False
return True
Dann einen einfachen Liste Verständnis oder Generator Ausdruck führen Sie Ihre Liste von vorrangiger zu bekommen,
[x for x in range(1,100) if isprime(x)]
Das scheint Hausaufgaben-y, also werde ich einen Hinweis, anstatt eine detaillierte Erklärung geben. Korrigieren Sie mich, wenn ich falsch angenommen haben.
Sie sind wohlauf so weit wie Rettung, wenn Sie einen noch Teiler zu sehen.
Aber Sie drucken ‚count‘, sobald Sie auch sehen ein Zahl, die nicht in sie nicht teilt. 2, zum Beispiel, teilt sich nicht gleichmäßig in 9. Aber das nicht 9a prime machen. Vielleicht möchten Sie gehen zu halten, bis Sie sicher sind, nicht Zahl im Bereich Streichhölzer.
(wie andere geantwortet haben, ist ein Sieb mit einem viel effizienteren Weg zu gehen ... nur versuchen, Ihnen zu helfen, zu verstehen, warum dieser spezifische Code tut nicht, was Sie wollen)
Wie wäre es damit, wenn Sie die Primzahl berechnen direkt:
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
Ein weiteres einfaches Beispiel mit einer einfachen Optimierung der nur ungerade Zahlen berücksichtigen. Alles getan, was mit Lazy-Streams (Python-Generatoren).
Verbrauch: Primzahlen = list (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
Hier ist eine Version von numpy Sieb des Eratosthenes sowohl Ordnung Komplexität aufweist (niedriger als ein Array mit der Länge n Sortierung) und Vektorisierung.
import numpy as np
def generate_primes(n):
is_prime = np.ones(n+1,dtype=bool)
is_prime[0:2] = False
for i in range(int(n**0.5)+1):
if is_prime[i]:
is_prime[i*2::i]=False
return np.where(is_prime)[0]
Timings:
import time
for i in range(2,10):
timer =time.time()
generate_primes(10**i)
print('n = 10^',i,' time =', round(time.time()-timer,6))
>> n = 10^ 2 time = 5.6e-05
>> n = 10^ 3 time = 6.4e-05
>> n = 10^ 4 time = 0.000114
>> n = 10^ 5 time = 0.000593
>> n = 10^ 6 time = 0.00467
>> n = 10^ 7 time = 0.177758
>> n = 10^ 8 time = 1.701312
>> n = 10^ 9 time = 19.322478
-
Die continue-Anweisung sieht falsch aus.
-
Sie möchten bei 2, da 2 ist die erste Primzahl ist.
starten
-
Sie können schreiben "während True:" eine Endlosschleife bekommen
.
Sie müssen sicherstellen, dass alle möglichen Teilern nicht teilen gleichmäßig die Anzahl Sie überprüfen. In diesem Fall werde drucken Sie die Nummer, die Sie jederzeit sind die Überprüfung nur eine der möglichen Teilern teilt sich nicht gleichmäßig die Nummer.
Sie wollen ja auch keine Aussage verwenden, fortgesetzt werden, da ein weiterhin nur es zu dem nächsten möglichen Divisor zu überprüfen, wenn Sie bereits herausgefunden, dass die Zahl keine Primzahl sind.
Hier ist, was ich habe:
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
Es ist ziemlich schnell für eine große Zahl, da es nur Kontrollen gegen bereits Primzahlen für Teilern einer Zahl.
Nun, wenn Sie eine Liste von Primzahlen erzeugen möchten, können Sie tun:
# 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
mit Generatoren hier könnte für Effizienz gewünscht werden.
Und gerade als Referenz, anstatt zu sagen:
one = 1
while one == 1:
# do stuff
Sie können einfach sagen:
while 1:
#do stuff
Sie können eine Liste von Primzahlen erstellen. Genommen von hier:
>>> noprimes = [j for i in range(2, 8) for j in range(i*2, 50, i)]
>>> primes = [x for x in range(2, 50) if x not in noprimes]
>>> print primes
>>> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
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
ähnlich wie user107745, aber ‚alle‘ statt doppelter Verneinung mit (etwas besser lesbar, aber ich denke, gleiche Leistung):
import math
[x for x in xrange(2,10000) if all(x%t for t in xrange(2,int(math.sqrt(x))+1))]
Im Grunde durchläuft es die x in Reichweite von mehr als (2, 100) und Kommissionierung nur diejenigen, die nicht mod == 0 für alle t in Bereich haben Sie (2, x)
Eine andere Art und Weise wahrscheinlich nur die Primzahlen bevölkern, wie wir gehen:
primes = set()
def isPrime(x):
if x in primes:
return x
for i in primes:
if not x % i:
return None
else:
primes.add(x)
return x
filter(isPrime, range(2,10000))
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
SymPy ist eine Python-Bibliothek für symbolische Mathematik. Es verfügt über einige Funktionen Primzahlen zu erzeugen.
isprime(n) # Test if n is a prime number (True) or not (False).
primerange(a, b) # Generate a list of all prime numbers in the range [a, b).
randprime(a, b) # Return a random prime number in the range [a, b).
primepi(n) # Return the number of prime numbers less than or equal to n.
prime(nth) # Return the nth prime, with the primes indexed as prime(1) = 2. The nth prime is approximately n*log(n) and can never be larger than 2**n.
prevprime(n, ith=1) # Return the largest prime smaller than n
nextprime(n) # Return the ith prime greater than n
sieve.primerange(a, b) # Generate all prime numbers in the range [a, b), implemented as a dynamically growing sieve of Eratosthenes.
Hier sind einige Beispiele.
>>> import sympy
>>>
>>> sympy.isprime(5)
True
>>> list(sympy.primerange(0, 100))
[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]
>>> sympy.randprime(0, 100)
83
>>> sympy.randprime(0, 100)
41
>>> sympy.prime(3)
5
>>> sympy.prevprime(50)
47
>>> sympy.nextprime(50)
53
>>> list(sympy.sieve.primerange(0, 100))
[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]
Wenn Sie wollte alle Primzahlen in einem Bereich finden Sie dies tun könnte:
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)
Just while its <= und Ihre Nummer für den Bereich hinzufügen.
OUTPUT:
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
Mit Generator:
def primes(num):
if 2 <= num:
yield 2
for i in range(3, num + 1, 2):
if all(i % x != 0 for x in range(3, int(math.sqrt(i) + 1))):
yield i
Verbrauch:
for i in primes(10):
print(i)
2, 3, 5, 7
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
Für mich sieht die folgende Lösung einfach und leicht zu folgen.
import math
def is_prime(num):
if num < 2:
return False
for i in range(2, int(math.sqrt(num) + 1)):
if num % i == 0:
return False
return True
