مولد بسيط بسيط في بيثون
https://stackoverflow.com/questions/567222
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
هل يمكن لأي شخص من فضلك قل لي ما أفعل الخطأ في هذا الرمز؟ انها مجرد طباعة "عدد" على أي حال. أريد فقط مولد بسيط للغاية (لا شيء يتوهم).
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
المحلول
هناك بعض المشاكل:
- لماذا تطبع العد عندما لم يقسم بواسطة X؟ هذا لا يعني أنه رئيسي، فهذا يعني فقط أن هذا X خاص لا يقسمه
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
من أجل جيل رئيسي أكثر كفاءة، راجع غربال EraStothenes، كما اقترح الآخرون. إليك تنفيذ لطيف ومحسن مع العديد من التعليقات:
# 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 في القائمة. كان بإمكاني استخدام غربال eratosthenes لكنك قلت أنك تريد شيئا بسيطا للغاية. ؛)
print [x for x in range(2,100) if not [t for t in range(2,x) if not x%t]]
re قوية:
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]
لاختبار ما إذا كان عدد رئيسي:
>>> 541 in primes(541)
True
>>> 543 in primes(543)
False
هنا بسيط (Python 2.6.2) الحل ... الذي يتماشى مع طلب OP الأصلي (الآن ستة أشهر)؛ ويجب أن يكون حلا مقبولا تماما في أي دورة "برمجة 101" ... وبالتالي هذا المنشور.
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
هذه الطريقة "القوة الغاشمة" البسيطة هي "سريعة بما يكفي" للأرقام حتى حوالي 16000 على الكمبيوتر الحديث (استغرق حوالي 8 ثوان على صندوقي 2 جيجا هرتز).
من الواضح أنه يمكن القيام بذلك بكثير بكثير بكثير، من خلال عدم إعادة حسابية كل عدد منها، أو كل مضاعف 3، 5، 7، إلخ لكل رقم واحد ... انظر غربال eratosthenes. (انظر تنفيذ إيليبن أعلاه)، أو حتى غربال اتكين إذا كنت تشعر بالشجاعة و / أو مجنون.
مفتاح التحذير: أنا بايثون مستجد. من فضلك لا تأخذ أي شيء أقوله بالإنجيل.
إلى رأيي، من الأفضل دائما اتخاذ النهج الوظيفي،
لذلك أقوم بإنشاء وظيفة أولا لمعرفة ما إذا كان الرقم رئيسا أم لا، ثم استخدمه في حلقة أو مكان آخر حسب الضرورة.
def isprime(n):
for x in range(2,n):
if n%x == 0:
return False
return True
ثم قم بتشغيل فهم قائمة أو تعبير مولد بسيط للحصول على قائمة Prime الخاصة بك،
[x for x in range(1,100) if isprime(x)]
ويبدو هذا الواجبات المنزلية، لذلك سأقدم تلميحا بدلا من تفسير مفصل. تصحيح لي إذا افترضت خطأ.
أنت بخير بقدر ما تنقذ عندما ترى مقسما.
لكنك تطبع "عد" بمجرد أن ترى حتى واحد الرقم الذي لا ينقسم فيه. 2، على سبيل المثال، لا يقسم بالتساوي إلى 9. ولكن هذا لا يجعل 9 رئيسا. قد ترغب في الاستمرار حتى أنت متأكد رقم رقم في المباريات النطاق.
(كما أجاب الآخرون، فإن غربال هي وسيلة أكثر فعالية للذهاب ... فقط محاولة لمساعدتك في فهم سبب عدم قيام هذا الرمز المحدد بما تريده)
ماذا عن هذا إذا كنت ترغب في حساب Prime مباشرة:
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
مثال بسيط آخر، مع تحسين بسيط للنظر في الأرقام الفردية فقط. كل شيء القيام به مع تدفقات كسول (مولدات بيثون).
الاستعمال: الأعداد الأولية = القائمة (إنشاء_prime_iterater (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
إليك نسخة Nutpy من غربال eratosthenes وجود تعقيد بخير (أقل من فرز مجموعة من الطول N) والتجهيزات.
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]
توقيت:
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
بيان الاستمرار تبدو خاطئة.
تريد أن تبدأ في 2 لأن 2 هو أول رقم رئيسي.
يمكنك الكتابة "بينما صحيح:" للحصول على حلقة لانهائية.
تحتاج إلى التأكد من أن جميع المقسورات المحتملة لا تقسم بالتساوي الرقم الذي تقوم بفحصه. في هذه الحالة، سطباعة الرقم الذي تقوم بفحص أي وقت واحد فقط من المقسورات المحتملين لا يقسم الرقم بالتساوي.
كما لا تريد استخدام عبارة متابعة لأن الاستمرار سوف يسبب ذلك فقط للتحقق من المقسني التالي الممكن عند اكتشافه بالفعل أن الرقم ليس رئيسا.
هنا ما لدي:
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
يمكنك إنشاء قائمة من الأعداد الأولية باستخدام قائمة الفهم بطريقة أنيقة إلى حد ما. مأخوذ من هنا:
>>> 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
على غرار user107745، ولكن باستخدام "الكل" بدلا من النفي المزدوج (أكثر قليلا مقروءة، لكنني أعتقد نفس الأداء):
import math
[x for x in xrange(2,10000) if all(x%t for t in xrange(2,int(math.sqrt(x))+1))]
في الأساس، يكرر على X في نطاق (2، 100) واختيار فقط أولئك الذين ليس لديهم mod == 0 لجميع T في النطاق (2، x)
ربما تكون هناك طريقة أخرى ملء الأرقام الرئيسية ونحن نذهب:
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
سيمبي هي مكتبة بيثون للرياضيات الرمزية. يوفر عدة وظائف لتوليد أرقام رئيسية.
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.
وهنا بعض الأمثلة.
>>> 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]
إذا كنت ترغب في العثور على جميع الأعداد الأولية في مجموعة، فيمكنك القيام بذلك:
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
باستخدام مولد:
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
الاستعمال:
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
بالنسبة لي، يبدو الحل أدناه بسيط وسهل اتباعه.
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
