Найти первые простые числа N в Python

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

#!/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

Этот код очень запутанный, и я не могу точно понять, о чем вы думали, когда писали его, или что пытались достичь. Первое, что я бы посоветовал, пытаясь понять, как кодировать, - это сделать имена переменных максимально описательными. Это поможет вам получить представление о том, что вы делаете, прямо в вашей голове, а также поможет любому, кто пытается помочь вам, показать вам, как реализовать ваши идеи.

При этом, вот пример программы который выполняет что-то близкое к цели:

primewanted = int(input("This program will give you the nth prime.\nPlease enter n:"))
if primewanted <= 0:
    print "n must be >= 1"
else:
    lastprime = 2 # 2 is the very first prime number
    primesfound = 1  # Since 2 is the very first prime, we've found 1 prime
    possibleprime = lastprime + 1 # Start search for new primes right after
    while primesfound < primewanted:
        # Start at 2.  Things divisible by 1 might still be prime
        testdivisor = 2
        # Something is still possibly prime if it divided with a remainder.
        still_possibly_prime = ((possibleprime % testdivisor) != 0)
        # (testdivisor + 1) because we never want to divide a number by itself.
        while still_possibly_prime and ((testdivisor + 1) < possibleprime):
            testdivisor = testdivisor + 1
            still_possibly_prime = ((possibleprime % testdivisor) != 0)
        # If after all that looping the prime is still possibly prime,
        # then it is prime.
        if still_possibly_prime:
            lastprime = possibleprime
            primesfound = primesfound + 1
        # Go on ahead to see if the next number is prime
        possibleprime = possibleprime + 1
    print "This nth prime is:", lastprime

Этот фрагмент кода:

        testdivisor = 2
        # Something is still possibly prime if it divided with a remainder.
        still_possibly_prime = ((possibleprime % testdivisor) != 0)
        # (testdivisor + 1) because we never want to divide a number by itself.
        while still_possibly_prime and ((testdivisor + 1) < possibleprime):
            testdivisor = testdivisor + 1
            still_possibly_prime = ((possibleprime % testdivisor) != 0)

можно было бы заменить несколько медленным, но, возможно, более понятным:

        # Assume the number is prime until we prove otherwise
        still_possibly_prime = True
        # Start at 2.  Things divisible by 1 might still be prime
        for testdivisor in xrange(2, possibleprime, 1):
            # Something is still possibly prime if it divided with a
            # remainder.  And if it is ever found to be not prime, it's not
            # prime, so never check again.
            if still_possibly_prime:
                still_possibly_prime = ((possibleprime % testdivisor) != 0)

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

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

Пока у нас не будет 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]

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

Вам нужно что-то вроде этого:

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 ()". ;) Подсказка: вам нужно только проверить деление со всеми ранее найденными простыми числами.

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

Для справки, существует довольно значительная разница в скорости между различными заявленными решениями. Вот сравнительный код. Решение, на которое указал Леннарт, называется "историческим", решение, предложенное Муравьем, называется "наивным", а решение RC называется "regexp".

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

Реализация сверхбыстрого сита от Дэвида Эпштейна - занимает 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])