Чтобы найти первые N простых чисел в Python

Question

Я новичок в мире программирования. Я просто писал этот код на python для генерации N простых чисел. Пользователь должен ввести значение для N, которое является общим числом простых чисел для распечатки. Я написал этот код, но он не выдает желаемый результат. Вместо этого он печатает простые числа до N-го числа. Например: пользователь вводит значение N = 7. Желаемый результат: 2, 3, 5, 7, 11, 13, 19 Фактический объем производства: 2, 3, 5, 7

Просьба сообщить.

i=1
x = int(input("Enter the number:"))
for k in range (1, (x+1), 1):
    c=0
    for j in range (1, (i+1), 1):
        a = i%j
        if (a==0):
            c = c+1

    if (c==2):
          print (i)
    else:
          k = k-1

    i=i+1

Answer 1

с использованием регулярного выражения:)

#!/usr/bin/python

import re, sys


def isPrime(n):
    # see http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/
    return re.match(r'^1?$|^(11+?)\1+$', '1' * n) == None


N = int(sys.argv[1]) # number of primes wanted (from command-line)
M = 100              # upper-bound of search space
l = list()           # result list

while len(l) < N:
    l += filter(isPrime, range(M - 100, M)) # append prime element of [M - 100, M] to l
    M += 100                                # increment upper-bound

print l[:N] # print result list limited to N elements

Answer 2

Сверхбыстрая реализация сита Дэвид Эппштейн - занимает 0,146 с за первые 1000 простых чисел на моем ПК:

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

primes = gen_primes()


x = set()
y = 0
a = gen_primes()
while y < 10000:
  x |= set([a.next()])
  y+=1

print "x contains {:,d} primes".format(len(x))
print "largest is {:,d}".format(sorted(x)[-1])

Answer 3

Для справки, существует довольно значительная разница в скорости между различными заявленными решениями. Вот код сравнения. Решение, на которое указывает Леннарт, называется «историческим», предложенное Антсом - «наивным», а решение RC - «регулярным выражением».

from sys import argv
from time import time

def prime(i, primes):
    for prime in primes:
        if not (i == prime or i % prime):
            return False
    primes.add(i)
    return i

def historic(n):
    primes = set([2])
    i, p = 2, 0
    while True:
        if prime(i, primes):
            p += 1
            if p == n:
                return primes
        i += 1

def naive(n):
    from itertools import count, islice
    primes = (n for n in count(2) if all(n % d for d in range(2, n)))
    return islice(primes, 0, n)

def isPrime(n):
    import re
    # see http://tinyurl.com/3dbhjv
    return re.match(r'^1?$|^(11+?)\1+$', '1' * n) == None

def regexp(n):
    import sys
    N = int(sys.argv[1]) # number of primes wanted (from command-line)
    M = 100              # upper-bound of search space
    l = list()           # result list

    while len(l) < N:
        l += filter(isPrime, range(M - 100, M)) # append prime element of [M - 100, M] to l
        M += 100                                # increment upper-bound

    return l[:N] # print result list limited to N elements

def dotime(func, n):
    print func.__name__
    start = time()
    print sorted(list(func(n)))
    print 'Time in seconds: ' + str(time() - start)

if __name__ == "__main__":
    for func in naive, historic, regexp:
        dotime(func, int(argv[1]))

Вывод этого на моей машине для n = 100:

naive
[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]
Time in seconds: 0.0219371318817
historic
[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]
Time in seconds: 0.00515413284302
regexp
[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]
Time in seconds: 0.0733318328857

Как видите, есть довольно большое расхождение. Здесь это снова для 1000 (основные выводы удалены):

naive
Time in seconds: 1.49018788338
historic
Time in seconds: 0.148319005966
regexp
Time in seconds: 29.2350409031

Answer 4

Линия k = k-1 не делает то, что вы думаете. Это не имеет никакого эффекта. Изменение k не влияет на цикл. На каждой итерации k присваивается следующему элементу диапазона, поэтому любые изменения, сделанные вами в k внутри цикла, будут перезаписаны.

Answer 5

Вот что я в итоге придумал, чтобы напечатать первые n простых чисел:

numprimes = raw_input('How many primes to print?  ')
count = 0
potentialprime = 2

def primetest(potentialprime):
    divisor = 2
    while divisor <= potentialprime:
        if potentialprime == 2:
            return True
        elif potentialprime % divisor == 0:
            return False
            break
        while potentialprime % divisor != 0:
            if potentialprime - divisor > 1:
                divisor += 1
            else:
                return True

while count < int(numprimes):
    if primetest(potentialprime) == True:
        print 'Prime #' + str(count + 1), 'is', potentialprime
        count += 1
        potentialprime += 1
    else:
        potentialprime += 1

Answer 6

То, что вы хотите, выглядит примерно так:

x = int(input("Enter the number:"))
count = 0
num = 2
while count < x:
     if isnumprime(x):
        print x
        count = count + 1
     num = num + 1

Я оставлю это на ваше усмотрение для реализации "isnumprime ()". ;) Подсказка: вам нужно только проверить деление со всеми найденными ранее номерами.

Answer 7

Использование выражений генератора для создания последовательности всех простых чисел и выделения 100-го числа из этого.

from itertools import count, islice
primes = (n for n in count(2) if all(n % d for d in range(2, n)))
print("100th prime is %d" % next(islice(primes, 99, 100)))

Answer 8

Пока у нас не будет N простых чисел, возьмите натуральные числа одно за другим, проверьте, делят ли их какие-либо из пока что собранных простых чисел.

Если никто не делает, "ууу", у нас есть новое простое число ...

вот и все.

>>> def generate_n_primes(N):
...     primes  = []
...     chkthis = 2
...     while len(primes) < N:
...         ptest    = [chkthis for i in primes if chkthis%i == 0]
...         primes  += [] if ptest else [chkthis]
...         chkthis += 1
...     return primes
...
>>> print generate_n_primes(15)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Answer 9

Вам нужен Prime Sieve (быстрый тип алгоритма для поиска простых чисел), очень простой - Sieve of Eratosthenes (см. Википедию), и здесь есть реализация на PHP http://www.scriptol.com/programming/sieve.php

Answer 10

def isPrime(y):
  i=2
  while i < y:
    if y%i == 0 :
      return 0
      exit()
    i=i+1
  return 1

x= raw_input('Enter the position 1st,2nd,..nth prime number you are looking for?: ')
z=int(x)
# for l in range(2,z)
count = 1
n = 2
while count <= z:
  if isPrime(n) == 1:
    if count == z:
      print n
    count +=1
  n=n+1