Чтобы найти первые 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

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

Answer 2

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

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

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) 

Answer 3

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

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

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

Answer 5

Что вы хотите что-то вроде этого:

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 6

До тех пор, пока у нас не будет 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 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

Для справки, существует довольно значительная разница в скорости между различными заявленными решениями.Вот пример кода сравнения. Решение, на которое указывает Леннарт, называется «историческим», тот, который предложен Муравьями, называется «наивным», а тот, который 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])) 

Выход этого на моей машине при п = 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 9

Супер быстрое внедрение решета по David Eppstein - принимает 0.146s для первых 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 10

Вот что я в конце концов пришел с напечатать первые п простых чисел:

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 11

n=int(input("Enter the number:: ")) 

for i in range(2,n): 
    p=i 
    k=0 
    for j in range(2,p-1): 
     if(p%j==0): 
      k=k+1 
    if(k==0): 
     print(p) 

Answer 12

Я не знаком с Python, так что я пишу часть счетчика C (слишком ленив, чтобы написать псевдокод ..: P) Чтобы найти первые n простых чисел .. // печатает все простые числа. не удосужившись сделать массив и вернуть его и т. д.

void find_first_n_primes(int n){ 
    int count = 0; 
    for(int i=2;count<=n;i++){ 
    factFlag == 0; //flag for factor count... 
    for(int k=2;k<sqrt(n)+1;k++){ 
     if(i%k == 0) // factor found.. 
     factFlag++; 
    } 
     if(factFlag==0)// no factors found hence prime.. 
     { 
     Print(i); // prime displayed.. 
     count++; 
     } 
    } 
} 

Answer 13

Это может помочь:

def in_prime(n): 
    p=True 
    i=2 
    if i**2<=n: 
     if n%i==0: 
      p=False 
      break 
    if (p): 
     return n 

Answer 14

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 

Answer 15

Это может помочь:

import sys 
from time import time 
def prime(N): 
    M=100 
    l=[] 
    while len(l) < N: 
     for i in range(M-100,M):  
      num = filter(lambda y :i % y == 0,(y for y in range(2 ,(i/2)))) 
      if not num and i not in [0,1,4]: 
       l.append(i) 
     M +=100 
    return l[:N] 


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


if __name__ == "__main__": 
    dotime(prime, int(sys.argv[1])) 

Answer 16

Вот са простая рекурсивная версия:

import datetime 
import math 

def is_prime(n, div=2): 
    if div> int(math.sqrt(n)): return True 
    if n% div == 0: 
     return False 
    else: 
     div+=1 
     return is_prime(n,div) 


now = datetime.datetime.now() 

until = raw_input("How many prime numbers my lord desires??? ") 
until = int(until) 

primelist=[] 
i=1; 
while len(primelist)<until: 
    if is_prime(i): 
     primelist.insert(0,i) 
     i+=1 
    else: i+=1 



print "++++++++++++++++++++" 
print primelist 
finish = datetime.datetime.now() 
print "It took your computer", finish - now , "secs to calculate it" 

Вот версия с использованием рекурсивной функции с памятью !:

import datetime 
import math 

def is_prime(n, div=2): 
    global primelist 
    if div> int(math.sqrt(n)): return True 
    if div < primelist[0]: 
     div = primelist[0] 
     for x in primelist: 
      if x ==0 or x==1: continue 
      if n % x == 0: 
       return False 
    if n% div == 0: 
     return False 
    else: 
     div+=1 
     return is_prime(n,div) 


now = datetime.datetime.now() 
print 'time and date:',now 

until = raw_input("How many prime numbers my lord desires??? ") 
until = int(until) 

primelist=[] 
i=1; 
while len(primelist)<until: 
    if is_prime(i): 
     primelist.insert(0,i) 
     i+=1 
    else: i+=1 



print "Here you go!" 
print primelist 

finish = datetime.datetime.now() 
print "It took your computer", finish - now , " to calculate it" 

Надеется, что это помогает :)

Answer 17

Попробуйте использовать во время цикла, чтобы проверить количество, то есть легко. Найдите фрагмент кода ниже:

i=1 
count = 0; 
x = int(input("Enter the number:\n")) 
while (count < x): 
c=0 
for j in range (1, (i+1), 1): 
    a = i%j 
    if (a==0): 
     c = c+1 

if (c==2): 
     print (i) 
     count = count+1 
i=i+1 

Answer 18

Во время воспроизведения с простыми числами в Python V3 я заметил, что наименьшее число, по которому композитный (не простое) число делится само всегда простое, что меньше площади корень из тестируемого числа.

Ниже приведена моя реализация этого поиска для вычисления первых N простых чисел.

первая тысяча простых чисел в 0.028S | первые 10 000 простых чисел в 0,6 | первые 100 000 простых чисел в 14.3S

Фрагмент внизу также показывает, сколько времени прошло поколение и распечатывает простые числа в хорошем формате таблицы.

import time 
import math 

def first_n_Primes(n): 
    number_under_test = 4 
    primes = [2,3] 
    while len(primes) < n: 
     check = False 
     for prime in primes: 
      if prime > math.sqrt(number_under_test) : break 
      if number_under_test % prime == 0: 
       check = True 
       break 
     if not check: 
      for counter in range(primes[len(primes)-1],number_under_test-1,2): 
       if number_under_test % counter == 0: 
        check = True 
        break 
     if not check: 
      primes.append(number_under_test) 
     number_under_test+=1 
    return primes 

start_time = time.time() 
data = first_n_Primes(1000) 
end_time = time.time() 

i = 1 
while i < len(data)+1: 
    print('{0: <9}'.format(str(data[i-1])), end="") 
    if i%10 == 0: print("") 
    i+=1 

print("\nFirst %d primes took %s seconds ---" % (len(data),end_time - start_time)) 

Answer 19

Это моя версия

import timeit 
import math 

__author__ = 'rain' 


primes = [2] 

def is_prime(n): 
    for prime in primes: 
     if n % prime == 0: 
      return False 
    return True 


def find_nth_prime(n): 
    current_index = 0 
    while(len(primes) < n): 
     if current_index == 0: 
      start_value = 3 
      end_value = 2 * 2 
     else: 
      start_value = primes[current_index - 1] * primes[current_index - 1] + 1 
      end_value = primes[current_index] * primes[current_index] 
     for i in range(start_value, end_value): 
      if is_prime(i): 
       primes.append(i) 
     current_index += 1 
    return primes[n-1] 


def solve(): 
    return find_nth_prime(10001) 

print solve() 

print timeit.timeit(solve, number=10) 

Я использую сито для сканирования простых чисел, это довольно быстро

Это займет всего 3.8e-06 секунд, чтобы получить 10001th прайм (10 раз).

Answer 20

Попробуйте это:

primeList = [] 
for num in range(2,10000): 
    if all(num%i!=0 for i in range(2,num)): 
     primeList.append(num) 
x = int(raw_input("Enter n: ")) 
for i in range(x): 
    print primeList[i] 

Answer 21

max = input("enter the maximum limit to check prime number"); 
if max>1 : 
    for i in range (2,max): 
     prime=0; 
     for j in range (2,i): 
      if(i%j==0): 
       prime=1; 
       break 
     if(prime==0 and i!=0): 
      print(i,"is prime number"); 
else: 
    print("prime no start from 2"); 

Answer 22

def Isprime(z): 
    '''returns True if the number is prime OTW returns false''' 
    if z<1: 
     return False 
    elif z==1: 
     return False 

    elif z==2: 
     return True 

    else: 
     for i in range(2,z): 
      if z%i==0: 
       return False 
      else: 
       return True 

Это так, как я это сделал. Конечно, есть так много способов сделать это.

Answer 23

prime=2 
counter = 0 
x = int(input("Enter the number:\n")) 
while (counter < x): 
    if all(prime%j!=0 for j in range(2, prime)): 
     print(prime, "is a prime number") 
     counter+=1 


    prime+=1 

Answer 24

Вы можете взять количество входов простого числа. Согласно вашему методу я взял здесь предопределенный счет 10:

i = 2 
if i == 2: 
    print(str(i) + "is a prime no") 
    i = i+1 
c=1 

while c<10: 
    for j in range(2, i): 
     if i%j==0: 
      break 

    if i == j+1: 
     print(str(i) + "is aa prime no") 
     c=c+1 

    i=i+1