python 점프투파이썬 %s - 파이썬의 간단한 총 생성기





11 Answers

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 개까지 목록으로 얻을 것입니다. 나는 에라 토 스테 네스 체를 사용할 수 있었지만, 당신은 매우 단순한 것을 원한다고 말했다. ;)

자료형 엔터입력 나누기

누군가이 코드로 내가 뭘 잘못하고 있는지 말해 줄 수 있습니까? 그것은 단지 '카운트'를 인쇄하는 것입니다. 나는 아주 단순한 소수 생성기를 원한다.

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



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]



다음은 OP의 원래 요청 (현재 6 개월 전)과 동일한 인스 트림 (파이썬 2.6.2) 솔루션입니다. 그리고 어떤 "프로그래밍 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

이 간단한 "무차별 대항"방법은 현대 PC에서 약 16,000 개까지의 숫자에 대해 "충분히 빠름"입니다 (2GHz 상자에서 약 8 초 소요).

분명히 이것은 모든 짝수의 우수성을 계산하지 않고 모든 단일 숫자에 대해 3, 5, 7 등의 모든 배수를 재 계산하지 않아 훨씬 효율적으로 수행 할 수 있습니다 ... en.wikipedia.org/wiki/Sieve_of_Eratosthenesen.wikipedia.org/wiki/Sieve_of_Eratosthenes 보십시오 (위의 eliben의 구현 참조). 특히 용감하고 미친 듯이 느껴지더라도 Atkin시브 (Sieve of Atkin) .

경고 Emptor : 저는 파이썬 놈입니다. 제발 제가 복음으로 말하는 것을 가져 가지 마십시오.




이것은 숙제 인 것처럼 보입니다. 그래서 자세한 설명보다는 힌트를 드리겠습니다. 내가 잘못했다고 생각하면 저를 바로 잡으십시오.

너는 심지어 공평한 약수를 보았을 때 구제 금융까지는 잘하고있다.

그러나 숫자로 나누지 않는 숫자를 보자 마자 '카운트'가 인쇄됩니다. 예를 들어 2는 9로 균등하게 나누지 않습니다. 그러나 9가 소수가되지는 않습니다. 해당 범위의 숫자가 일치 하지 않을 때까지 계속 갈 수도 있습니다.

(다른 사람들이 대답했듯이 시브 (Sieve)는 훨씬 더 효율적인 방법입니다 ... 왜이 특정 코드가 원하는 것을하지 않는지 이해하는 데 도움이됩니다)




홀수를 고려하는 단순한 최적화를 사용한 또 다른 간단한 예입니다. 모든 것이 게으른 스트림 (파이썬 생성기)에서 수행됩니다.

사용법 : 소수 = 목록 (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



가능한 모든 약수가 당신이 검사하는 번호를 균등하게 나누지 않는지 확인해야합니다. 이 경우 언제든지 확인할 수있는 번호를 인쇄하여 가능한 약수 중 하나만 번호를 균등하게 나누지 않습니다.

또한 continue 문은 number가 소수가 아니라는 것을 이미 알아 냈을 때 continue가 다음 가능한 제수를 확인하게하기 때문에 continue 문을 사용하고 싶지 않습니다.




List comprehensions을 사용하여 매우 우아한 방식으로 소수의리스트를 만들 수 있습니다. here: 에서 가져온 here:

>>> 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]



user107745와 비슷하지만 double negation 대신 '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))



SymPy 는 상징적 인 수학을위한 Python 라이브러리입니다. 프라임 숫자를 생성하는 몇 가지 함수를 제공합니다.

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]



여기에 괜찮은 복잡성 (길이 n의 배열을 정렬하는 것보다 낮음)과 벡터화를 모두 가지고있는 에라 토 스테 네스의 시브 (Sieve of Eratosthenes)가 있습니다.

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



나에게있어 아래의 솔루션은 간단하고 쉽게 따라 할 수 있습니다.

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



Related