Eenvoudige priemgetalgenerator in Python

Kan iemand mij vertellen wat ik verkeerd doe met deze code? Het is toch gewoon ‘count’ printen. Ik wil gewoon een heel eenvoudige prime-generator (niets bijzonders).

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

Antwoord 1, autoriteit 100%

Er zijn enkele problemen:

• Waarom print je het aantal uit als het niet door x is gedeeld? Het betekent niet dat het priemgetal is, het betekent alleen dat deze specifieke x het niet deelt
• continuegaat naar de volgende lus-iteratie – maar u wilt deze echt stoppen door break

te gebruiken

Hier is je code met een paar verbeteringen, het drukt alleen priemgetallen af:

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

Voor een veel efficiëntere generatie van priemgetallen, zie de zeef van Eratosthenes, zoals anderen hebben gesuggereerd. Hier is een mooie, geoptimaliseerde implementatie met veel opmerkingen:

# 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

Merk op dat het een generator retourneert.

Antwoord 2, autoriteit 8%

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]

We krijgen alle priemgetallen tot 20 in een lijst.
Ik had Sieve of Eratosthenes kunnen gebruiken, maar je zei:
je wilt iets heel eenvoudigs. 😉

Antwoord 3, autoriteit 8%

re is krachtig:

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]

Antwoord 4, autoriteit 5%

print [x for x in range(2,100) if not [t for t in range(2,x) if not x%t]]

Antwoord 5, autoriteit 5%

def primes(n): # simple sieve of multiples 
   odds = range(3, n+1, 2)
   sieve = set(sum([list(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]

Om te testen of een getal een priemgetal is:

>>> 541 in primes(541)
True
>>> 543 in primes(543)
False

Antwoord 6, autoriteit 2%

Hier is een eenvoudige(Python 2.6.2) oplossing… die in lijn is met het oorspronkelijke verzoek van het OP (nu zes maanden oud); en zou een perfect acceptabele oplossing moeten zijn in elke cursus “programmeren 101” … Vandaar dit bericht.

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

Deze eenvoudige “brute force”-methode is “snel genoeg” voor getallen tot ongeveer 16.000 op moderne pc’s (duurde ongeveer 8 seconden op mijn 2GHz-box).

Uiteraard kan dit veel efficiënter worden gedaan, door niet het priemgetal van elk even getal, of elk veelvoud van 3, 5, 7, enz. voor elk afzonderlijk getal opnieuw te berekenen… Zie de Zeef van Eratosthenes(zie de implementatie van eliben hierboven), of zelfs de Zeef van Atkinals je je bijzonder dapper en/of gek voelt.

Voorbehoud Emptor: ik ben een python-noob. Beschouw alsjeblieft niets van wat ik zeg als evangelie.

Antwoord 7, autoriteit 2%

SymPyis een Python-bibliotheek voor symbolische wiskunde. Het biedt verschillende functies om priemgetallen te genereren.

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 zijn enkele voorbeelden.

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

Antwoord 8

Hier is een numpy-versie van Sieve of Eratosthenes met zowel een redelijke complexiteit (lager dan het sorteren van een array met lengte n) als vectorisatie.

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]

Timingen:

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

Antwoord 9

python 3 (genereer priemgetal)

import math
i = 2
while True:
    for x in range(2, int(math.sqrt(i) + 1)):
        if i%x==0:
            break
    else:
        print(i)
    i += 1

Antwoord 10

Dit is wat ik heb:

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

Het is vrij snel voor grote getallen, omdat het alleen controleert tegen reeds priemgetallen voor delers van een getal.

Als u nu een lijst met priemgetallen wilt genereren, kunt u het volgende doen:

# 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

het gebruik van generatoren hier kan wenselijk zijn voor efficiëntie.

En alleen ter referentie, in plaats van te zeggen:

one = 1
while one == 1:
    # do stuff

je kunt gewoon zeggen:

while 1:
    #do stuff

Antwoord 11

Naar mijn mening is het altijd het beste om de functionele benadering te volgen,

Dus ik maak eerst een functie om erachter te komen of het getal een priemgetal is of niet, en gebruik het dan in een lus of op een andere plaats als dat nodig is.

def isprime(n):
      for x in range(2,n):
        if n%x == 0:
            return False
    return True

Voer vervolgens een eenvoudig lijstbegrip of generatoruitdrukking uit om uw lijst met prime-,

. te krijgen

[x for x in range(1,100) if isprime(x)]

Antwoord 12

Nog een eenvoudig voorbeeld, met een eenvoudige optimalisatie van alleen oneven getallen. Alles gedaan met luie streams (python-generators).

Gebruik: priemgetallen = lijst(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

Antwoord 13

Dit is mijn implementatie. Ik weet zeker dat er een efficiëntere manier is, maar het lijkt te werken. Basis vlaggebruik.

def genPrime():
    num = 1
    prime = False
    while True:
        # Loop through all numbers up to num
        for i in range(2, num+1):
            # Check if num has remainder after the modulo of any previous numbers
            if num % i == 0:
                prime = False
                # Num is only prime if no remainder and i is num
                if i == num:
                    prime = True
                break
        if prime:
            yield num
            num += 1
        else:
            num += 1
prime = genPrime()
for _ in range(100):
    print(next(prime))

Antwoord 14

Net het onderwerp bestudeerd, zoek naar de voorbeelden in de thread en probeer mijn versie te maken:

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,
        ),
    )

Het resultaat van het uitvoeren van deze code laat interessante resultaten zien:

$ 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

Dus ik kan zien dat we hier de juiste antwoorden hebben op verschillende vragen; voor een priemgetalgenerator lijkt gen_primeshet juiste antwoord; maar voor een priemgetalcontrole is de functie simple_is_primebeter geschikt.

Dit werkt, maar ik sta altijd open voor betere manieren om is_primete laten functioneren.

Antwoord 15

Je moet ervoor zorgen dat alle mogelijke delers het getal dat je controleert niet gelijk verdelen. In dit geval print je het getal dat je aan het controleren bent op elk moment dat slechts een van de mogelijke delers het getal niet gelijk verdeelt.

Je wilt ook geen continue-statement gebruiken, omdat een continue er alleen maar voor zorgt dat de volgende mogelijke deler wordt gecontroleerd als je al hebt ontdekt dat het getal geen priemgetal is.

Antwoord 16

Dit lijkt huiswerk, dus ik zal een hint geven in plaats van een gedetailleerde uitleg. Corrigeer me als ik het verkeerd heb aangenomen.

Je doet het prima wat betreft redding als je een even deler ziet.

Maar je drukt ‘tellen’ af zodra je zelfs maar ééngetal ziet dat er niet in kan worden gedeeld. 2, bijvoorbeeld, is niet gelijk verdeeld in 9. Maar dat maakt 9 nog geen priemgetal. Misschien wilt u doorgaan totdat u zeker weet dat geennummer in het bereik overeenkomt.

(zoals anderen hebben geantwoord, is een zeef een veel efficiëntere manier om te gaan… ik probeer je alleen te helpen begrijpen waarom deze specifieke code niet doet wat je wilt)

Antwoord 17

Je kunt op een redelijk elegante manier een lijst met priemgetallen maken met behulp van lijstbegrippen. Genomen van 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]

Antwoord 18

Wat dacht je hiervan als je het priemgetal rechtstreeks wilt berekenen:

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

Antwoord 19

Vergelijkbaar met user107745, maar met ‘all’ in plaats van dubbele ontkenning (een beetje leesbaarder, maar ik denk dezelfde prestaties):

import math
[x for x in xrange(2,10000) if all(x%t for t in xrange(2,int(math.sqrt(x))+1))]

In principe itereert het over de x in het bereik van (2, 100) en kiest alleen die welke geen mod == 0 hebben voor alle t in het bereik (2,x)

Een andere manier is waarschijnlijk om de priemgetallen gaandeweg in te vullen:

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

Antwoord 20

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

Antwoord 21

Als je alle priemgetallen in een bereik wilt vinden, kun je dit doen:

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)

Voeg gewoon while its <=is en uw nummer voor het bereik.
UITGANG:
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

Antwoord 22

Generator gebruiken:

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

Gebruik:

for i in primes(10):
    print(i)

2, 3, 5, 7

Antwoord 23

• Het vervolg-statement ziet er niet goed uit.

• Je wilt bij 2 beginnen omdat 2 het eerste priemgetal is.

• Je kunt “while True:” schrijven om een ​​oneindige lus te krijgen.

Antwoord 24

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

Antwoord 25

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

Antwoord 26

Voor mij ziet de onderstaande oplossing er eenvoudig en gemakkelijk te volgen uit.

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