12

我是编程世界的新手。我只是在 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):
    c = 0
    for j in range(1, i+1):
        a = i % j
        if a == 0:
            c = c + 1

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

    i = i + 1
4

30 回答 30

32

使用正则表达式:)

#!/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
于 2009-10-27T06:38:26.570 回答
15

作为参考,各种规定的解决方案之间存在相当显着的速度差异。这是一些比较代码。Lennart 提出的解决方案称为“historic”,Ants 提出的解决方案称为“naive”,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
于 2009-10-28T16:31:43.150 回答
15

David Eppstein实现的超快速筛分- 我的 PC 上的前 1000 个素数需要 0.146 秒:

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])
于 2010-02-06T11:28:37.363 回答
7

这条线k = k-1并没有按照你的想法做。它没有效果。更改k不会影响循环。在每次迭代中,k将分配给范围的下一个元素,因此您k在循环内所做的任何更改都将被覆盖。

于 2009-10-27T05:49:26.093 回答
4

你想要的是这样的:

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

我将由您来实现isnumprime();) 提示:您只需要使用所有先前找到的素数来测试除法。

于 2009-10-27T08:38:09.117 回答
4

这是我最终想出的打印前 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
        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
于 2012-09-17T06:24:09.317 回答
3

直到我们有 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]
于 2009-10-27T12:02:22.690 回答
3

使用生成器表达式创建所有素数的序列并从中切出第 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)))
于 2009-10-27T20:01:40.970 回答
1
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
于 2013-05-29T18:19:45.957 回答
1

您可以输入素数的数量。根据您的方法,我在这里采用了预定义的 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
于 2018-01-03T16:05:32.323 回答
1

最快的

import math

n = 10000 #first 10000 primes
tmp_n = 1
p = 3
primes = [2]

while tmp_n < n:

    is_prime = True
    for i in range(3, int(math.sqrt(p) + 1), 2):
        # range with step 2

        if p % i == 0:
            is_prime = False

    if is_prime:
        primes += [p]
        tmp_n += 1

    p += 2

print(primes)
于 2021-02-15T12:28:15.260 回答
0

尝试使用 while 循环来检查计数,这很容易。找到下面的代码片段:

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
于 2014-07-22T00:03:36.037 回答
0

这可能会有所帮助:

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]))
于 2013-09-06T10:34:24.203 回答
0

这段代码非常混乱,我无法弄清楚你在编写它时到底在想什么,或者你试图完成什么。在试图弄清楚如何编码时,我建议的第一件事是首先让你的变量名具有极强的描述性。这将帮助您直接在脑海中了解您正在做的事情,它还将帮助任何试图帮助您向您展示如何让您的想法正确的人。

话虽如此,这里有一个示例程序可以完成接近目标的事情:

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)
于 2009-10-27T05:58:12.503 回答
0

Here's a simple recursive version:

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"

Here's a version using a recursive function with memory!:

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"

Hope it helps :)

于 2013-10-15T11:24:44.733 回答
0
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)
于 2012-10-29T07:13:07.550 回答
0
count = -1
n = int(raw_input("how many primes you want starting from 2 "))
primes=[[]]*n
for p in range(2, n**2):
    for i in range(2, p):
        if p % i == 0:
            break
    else:
        count +=1
        primes[count]= p
        if count == n-1:
            break

print (primes)
print 'Done'
于 2018-07-18T13:25:41.143 回答
0
#!/usr/bin/python3
import sys

primary_numbers = [1, 2]


def is_prime(i):
    for pn in enumerate(primary_numbers[2:]):
        if i % pn[1] == 0:
            return False

    return True

def main(position):
    i = 3
    while len(primary_numbers) < int(position):
        print(i)
        res = is_prime(i)
        if res:
            primary_numbers.append(i)
        i += 2


if __name__ == '__main__':
    position = sys.argv[1]
    main(position)
    print(primary_numbers)
于 2019-05-14T14:25:19.380 回答
0

这里的答案很简单,即运行循环“n”次。

n=int(input())
count=0
i=2
while count<n:
    flag=0
    j=2
    while j<=int(i**0.5):
        if i%j==0:
            flag+=1
        j+=1
    if flag==0:
        print(i,end=" ")
        count+=1
    i+=1
于 2018-08-13T17:50:20.370 回答
0
def isprime(n):
    if n <= 1:
        return False
    for x in range(2, n):
        if n % x == 0:
            return False
    else:
        return True

def list_prime(z):
    y = 0
    def to_infinity():
        index=0
        while 1:
            yield index
            index += 1
    for n in to_infinity():
        if y < z:
            if isprime(n):
                y = y + 1
                print(n, end='\n', flush=True)
        else:break
    print(f'\n {z} prime numbers are as above.')

# put your range below
list_prime(10)
于 2019-09-06T05:50:38.320 回答
0

这是我的版本

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 秒即可获得第 10001 个素数(10 次)。

于 2015-11-04T02:55:46.980 回答
0

在 Python V3 中使用素数时,我注意到复合(非素数)可整除的最小数本身始终是小于被测数平方根的素数。

下面是我对计算前 N 个素数的发现的实现。

0.028S 内的前 1,000 个素数 | 0.6S 内的前 10,000 个素数 | 14.3S 中的前 100,000 个素数

下面的代码片段还显示了生成需要多长时间,并以漂亮的表格格式打印出素数。

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))
于 2015-09-01T11:45:13.330 回答
0
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");
于 2017-03-25T17:05:10.213 回答
0
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
于 2017-09-25T01:55:38.597 回答
0

尝试这个:

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]
于 2016-02-23T11:55:18.380 回答
-1

我不熟悉 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++;
        }
   }
}
于 2013-03-19T09:58:28.573 回答
-1

这可能会有所帮助:

def in_prime(n):
    p=True
    i=2
    if i**2<=n:
        if n%i==0:
            p=False
            break
    if (p):
        return n
于 2013-04-24T17:57:35.613 回答
-1

你好!我对编码很陌生,刚开始 4 天。我写了一个代码来返回前 1000 个素数,包括 1。看看

n=1
c=0
while n>0:
   for i in range(2,n):
      if n%i == 0:
         break
   else:
      print(n,'is a prime')
      c=c+1
   n=n+1
   if c==1000:
      break
于 2019-06-08T09:50:31.633 回答
-1
#Simple python program to print N prime numbers 

    inp = int(input("required prime numbers"))
    list =set ()
    num =1
    while(1):
      for i in range(2,num):
         if num%i==0:
            #print("not prime")
            break
      else:
          #print("prime")
          list.add(num)    
      if len(list)<inp:
          num=num+1
      else:
          break
    print("n primes:",list)
于 2021-12-01T11:10:53.813 回答
-3
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

我就是这样做的。当然,有很多方法可以做到。

于 2017-05-22T05:56:44.350 回答