파이썬의 간단한 프라임 생성자
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
몇 가지 수정 사항이있는 코드는 다음과 같습니다. Primes 만 인쇄합니다.
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의 원래 요청과 인라인 (현재 6 개월 된); 그리고 "프로그래밍 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
이 간단한 "Brute Force"방법은 현대 PC에서 약 16,000 명까지 최대 약 16,000 명 (2GHz 상자에서 약 8 초가 걸렸습니다).
분명히, 이것은 모든 짝수의 짝수 또는 3, 5, 7 등의 모든 배수를 단일 숫자에 대해 다시 계산하지 않음으로써 훨씬 더 효율적으로 수행 될 수 있습니다. 에라 토스 테네스의 체 (위의 Eleiben의 구현 참조) 또는 심지어 Atkin의 체 당신이 특히 용감하고/또는 미친 느낌이라면.
경고 emptor : 나는 파이썬 멍청이입니다. 제가 복음으로 말하는 것을 가져 가지 마십시오.
제 생각에는 항상 기능적 접근 방식을 취하는 것이 가장 좋습니다.
따라서 숫자가 프라임인지 아닌지를 찾아서 먼저 함수를 만듭니다. 그런 다음 루프 나 다른 장소에서 필요에 따라 사용합니다.
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)]
이것은 숙제처럼 보이므로 자세한 설명보다는 힌트를 줄 것입니다. 내가 틀렸다고 가정하면 나를 수정하십시오.
당신은 짝수의 제수를 볼 때 구제하는 한 멀리 잘하고 있습니다.
하지만 당신은 당신이 보는 즉시 'count'를 인쇄하고 있습니다. 하나 그것으로 나누지 않는 숫자. 예를 들어, 2는 9로 균등하게 나누지 않습니다. 그러나 그것은 9를 프라임으로 만들지 않습니다. 당신은 확실 할 때까지 계속 가고 싶을 수도 있습니다 아니요 범위의 숫자는 일치합니다.
(다른 사람들이 대답했듯이, 체는 훨씬 더 효율적인 방법입니다 ...이 특정 코드가 원하는 것을 수행하지 않는 이유를 이해하도록 돕는 것만으로도
프라임을 직접 계산하려면 다음과 같습니다.
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
또 다른 간단한 예, 홀수를 고려하는 간단한 최적화로. 게으른 스트림 (Python Generators)으로 모든 작업.
사용법 : primes = 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
다음은 괜찮은 복잡성 (길이 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에서 시작하려고합니다.
무한 루프를 얻기 위해 "True :"를 쓸 수 있습니다.
가능한 모든 제수가 확인한 번호를 고르게 나누지 않도록해야합니다. 이 경우 가능한 제수 중 하나만이 숫자를 균등하게 나누지 않을 때마다 확인할 숫자를 인쇄합니다.
또한 계속 명령문을 사용하고 싶지 않기 때문에 계속해서 숫자가 프라임이 아니라는 것을 알았을 때 다음 가능한 제수를 확인하게됩니다.
다음은 다음과 같습니다.
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와 유사하지만 이중 부정 대신 'All'을 사용합니다 (조금 더 읽기 쉽지만 동일한 성능이라고 생각합니다) :
import math
[x for x in xrange(2,10000) if all(x%t for t in xrange(2,int(math.sqrt(x))+1))]
기본적으로 (2, 100) 범위에서 x를 반복하고 (2, x) 범위의 모든 t에 대해 mod == 0을 갖지 않는 것을 선택합니다.
또 다른 방법은 아마도 우리가 갈 때 소수를 채우는 것입니다.
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
