11 
count = 0
i = 11

while count <= 1000 and i <= 10000:
    if i%2 != 0:
       if (i%3 == 0 or i%4 == 0 or i%5 == 0 or i%6 == 0 or i%7 == 0 or i%9 == 0):
           continue
       else:
           print i,'is prime.'
           count += 1
    i+=1

我试图仅通过使用循环来生成第 1000 个素数。我正确地生成了素数，但我得到的最后一个素数不是第 1000 个素数。我如何修改我的代码来做到这一点。提前感谢您的帮助。

编辑：我现在明白如何解决这个问题。但是有人可以解释为什么下面的代码不起作用吗？这是我在这里发布第二个代码之前编写的代码。

count = 1
i = 3
while count != 1000:
    if i%2 != 0:
       for k in range(2,i):
          if i%k == 0:
            print(i)
            count += 1
            break
     i += 1
4

13 回答 13

9

让我们来看看。

count = 1
i = 3
while count != 1000:
    if i%2 != 0:
       for k in range(2,i):
          if i%k == 0:        # 'i' is _not_ a prime!
            print(i)       # ??
            count += 1     # ??
            break
     i += 1          # should be one space to the left,
                     # for proper indentation

如果i%k==0，则i不是素数。如果我们检测到它不是素数，我们应该（a）不打印出来，（b）不增加找到的素数的计数器，（c）我们确实应该跳出for循环——不需要测试更多的数字。

i%2另外，我们可以不用 testing ，而是2从 开始递增，3然后它们都将是奇数，通过构造。

所以，我们现在有

count = 1
i = 3
while count != 1000:
    for k in range(2,i):
        if i%k == 0:       
            break
    else:
        print(i)
        count += 1
    i += 2

如果循环没有过早中断，则执行elseafter 。forfor

它可以工作，但是工作太辛苦，因此比必要的要慢得多。它通过它下面的所有数字来测试一个数字，但是仅仅测试它的平方根就足够了。为什么？因为如果一个数字n == p*q,p和q之间1,n那么至少有一个p或q将不大于 的平方根n：如果它们都大于 ，则它们的乘积将大于n。

所以改进的代码是：

from math import sqrt

count = 1
i = 1
while count < 1000:
    i += 2
    for k in range(2, 1+int(sqrt(i+1))):
        if i%k == 0:       
            break
    else:
        # print(i) ,
        count += 1
        # if count%20==0: print ""
print i

试着用range(2,i)（如前面的代码）运行它，看看它有多慢。对于 1000 个素数，需要 1.16 秒，对于 2000 – 4.89 秒（3000 – 12.15 秒）。但是生成3000 个素sqrt数只需要 0.21 秒，10,000 个素数需要 0.84 秒，20,000 个素数需要 2.44 秒（与.的增长数量级）。~ n2.1...2.2~ n1.5

上面使用的算法称为试除法。要使其成为最佳试验部门，还需要进一步改进，即仅通过素数进行测试。可以在此处看到一个示例，它的运行速度提高了大约 3 倍，并且经验复杂度为 .~ n1.3

然后是 Eratosthenes 的筛子，它的速度相当快（对于 20,000 个素数，比上面的“改进代码”快 12 倍，之后还要快得多：它的经验增长顺序是，对于产生素数，测量到n = 1,000,000 个素数):~ n1.1n

from math import log

count = 1 ; i = 1 ; D = {}
n = 100000                        # 20k:0.20s 
m = int(n*(log(n)+log(log(n))))   # 100k:1.15s 200k:2.36s-7.8M 
while count < n:                  #            400k:5.26s-8.7M 
        i += 2                    #            800k:11.21-7.8M 
        if i not in D:            #            1mln:13.20-7.8M (n^1.1)
            count += 1
            k = i*i
            if k > m:  break      # break, when all is already marked
            while k <= m:
                D[k] = 0 
                k += 2*i
while count < n:
        i += 2
        if i not in D: count += 1
if i >= m: print "invalid: top value estimate too small",i,m ; error
print i,m

埃拉托色尼的真正无界、增量、“滑动”筛网速度快了大约 1.5 倍，在此测试的这个范围内。

于 2013-03-14T22:44:15.337 回答
5

有几个问题是显而易见的。首先，因为你从 11 开始，你已经跳过了前 5 个素数，所以 count 应该从 5 开始。

更重要的是，您的主要检测算法无法正常工作。您必须跟踪所有小于 i 的素数，才能进行这种简单的“埃拉托斯坦筛”式素数检测。例如，您的算法会认为 11 * 13 = 143 是素数，但显然不是。

这里的PGsimple1是您在此处尝试进行的主要检测的正确实现，但那里的其他算法要快得多。

于 2013-03-14T02:35:39.997 回答
3

你确定你正确地检查素数吗？一个典型的解决方案是有一个你知道有效的单独的“isPrime”函数。

def isPrime(num):
    i = 0
    for factor in xrange(2, num):
        if num%factor == 0:
            return False
    return True

（有一些方法可以使上述功能更有效，例如只检查赔率，只检查平方根以下的数字等）

然后，要找到第 n 个素数，计算所有素数，直到找到它：

def nthPrime(n):
    found = 0
    guess = 1
    while found < n:
        guess = guess + 1
        if isPrime(guess):
            found = found + 1
    return guess
于 2013-03-14T02:42:58.890 回答
2

你的逻辑不太正确。尽管 ：

if i%2 != 0:
    if (i%3 == 0 or i%4 == 0 or i%5 == 0 or i%6 == 0 or i%7 == 0 or i%9 == 0):

这不能判断一个数是否是素数。

我认为您应该检查 sqrt(i) 以下的所有数字是否除以 i 。

于 2013-03-14T02:33:50.920 回答
1

这是我在某处遇到的 is_prime 函数，可能是在 SO 上。

def is_prime(n):
  return all((n%j > 0) for j in xrange(2, n))

primes = []

n = 1
while len(primes) <= 1000: 
    if is_prime(n):
        primes.append(n)
    n += 1

或者，如果您希望所有内容都在循环中，只需使用 is_prime 函数的返回即可。

primes = []    
n = 1
while len(primes) <= 1000: 
    if all((n%j > 0) for j in xrange(2, n)):
        primes.append(n)
    n += 1
于 2013-03-14T02:35:42.267 回答
0

这可能更快：尝试将 num 从 2 划分为 sqrt(num)+1 而不是 range(2,num)。

from math import sqrt

i = 2 
count = 1

while True:
    i += 1
    prime = True
    div = 2
    limit = sqrt(i) + 1
    while div < limit:
        if not (i % div):
            prime = False
            break
        else:
            div += 1
    if prime:
        count += 1
    if count == 1000:
        print "The 1000th prime number is %s" %i
        break
于 2013-03-14T02:52:31.960 回答
0

试试这个：

def isprime(num):
    count = num//2 + 1
    while count > 1:
        if num %count == 0:
            return False
        count -= 1
    else:
        return True

num = 0
count = 0
while count < 1000:
    num += 1
    if isprime(num):
        count += 1
    if count == 1000:
        prime = num

您的代码存在问题：

  1. 无需检查 i <= 10000。

  2. 你正在这样做

    if i%2 != 0:
    if (i%3 == 0 or i%4 == 0 or i%5 == 0 or i%6 == 0 or i%7 == 0 or i%9 == 0):

    在这里，您没有检查该数字是否可被大于 7 的素数整除。因此，您的结果：最有可能被 11 整除

  3. 因为 2. 你的算法说 17 * 13 * 11 是一个素数（它不是）

于 2013-03-14T04:08:39.177 回答
0

这个怎么样：

#!/usr/bin/python

from math import sqrt

def is_prime(n):
    if n == 2:
        return True
    if (n < 2) or (n % 2 == 0):
        return False
    return all(n % i for i in xrange(3, int(sqrt(n)) + 1, 2))

def which_prime(N):
    n = 2
    p = 1
    while True:
        x = is_prime(n)
        if x:
            if p == N:
                return n
            else:
                p += 1
        n += 1
print which_prime(1000)
于 2013-12-28T03:50:21.503 回答
0 
n=2                         ## the first prime no.
prime=1                     ## we already know 2 is the first prime no.
while prime!=1000:          ## to get 1000th prime no.
    n+=1                    ## increase number by 1
    pon=1                   ## sets prime_or_not(pon) counter to 1
    for i in range(2,n):    ## i varies from 2 to n-1
        if (n%i)==0:        ## if n is divisible by i, n is not prime
            pon+=1          ## increases prime_or_not counter if  n is not prime
    if pon==1:              ## checks if n is prime or not at the end of for loop
        prime+=1            ## if n is prime, increase prime counter by 1
print n                     ## prints the thousandth prime no.
于 2014-06-12T07:14:13.683 回答
0

这是另一个提交：

ans = 0;
primeCounter = 0;
while primeCounter < 1000:
    ans += 1;    
    if ans % 2 != 0: 
        # we have an odd number
        # start testing for prime
        divisor = 2;
        isPrime = True;
        while divisor < ans:
            if ans % divisor == 0: 
                isPrime = False;
                break;
            divisor += 1;
        if isPrime:             
            print str(ans) + ' is the ' + str(primeCounter) + ' prime';
            primeCounter += 1;
print 'the 1000th prime is ' + str(ans);
于 2014-08-05T17:16:25.847 回答
0

这是一种仅使用 if & while 循环的方法。这将只打印出第 1000 个素数。它跳过了 2。我将其作为麻省理工学院 OCW 6.00 课程的问题集 1 来完成，因此仅包括第二堂课之前教授的命令。

prime_counter = 0  
number = 3  

while(prime_counter < 999):
    divisor = 2
    divcounter = 0
    while(divisor < number):
        if(number%divisor == 0):
            divcounter = 1  
        divisor += 1
    if(divcounter == 0):
        prime_counter+=1
    if(prime_counter == 999):
        print '1000th prime number: ', number
    number+=2
于 2016-09-22T11:03:48.030 回答
0

我刚写了这个。它会询问您想要查看多少个素数用户，在这种情况下它将是 1000。随意使用它:)。

# p is the sequence number of prime series
# n is the sequence of natural numbers to be tested if prime or not
# i is the sequence of natural numbers which will be used to devide n for testing
# L is the sequence limit of prime series user wants to see
p=2;n=3
L=int(input('Enter the how many prime numbers you want to see: '))
print ('# 1  prime is 2')
while(p<=L):
    i=2
    while i<n:
        if n%i==0:break
        i+=1
    else:print('#',p,' prime is',n); p+=1
    n+=1 #Line X

#when it breaks it doesn't execute the else and goes to the line 'X'
于 2016-12-01T03:55:43.577 回答
0

这将是执行次数较少的优化代码，它可以在一秒钟内计算和显示 10000 个素数。它将显示所有素数，如果只需要第 n 个素数，只需设置 while 条件并在退出循环后打印素数。如果你想检查一个数字是质数还是不只是将数字分配给n，并删除while循环..它使用质数属性*如果一个数字不能被小于其平方根的数字整除，那么它是素数。* 而不是检查到最后（意味着 1000 次迭代以确定 1000 是否是素数）我们可以在 35 次迭代内结束循环，* break如果它在开始时被任何数字除以循环（如果它是偶数循环将在第一次迭代时中断，如果它可以被 3 整除然后是 2 次迭代）所以我们只为素数迭代直到结束

记住一件事你仍然可以通过使用属性优化迭代，也很难找到一个特定的数字是不是素数，所以这将是最好的逻辑或代码

import math
number=1
count = 0

while(count<10000):
    isprime=1
    number+=1
    for j in range(2,int(math.sqrt(number))+1):
        if(number%j==0):
            isprime=0   
            break
    if(isprime==1):
        print(number,end=" ")
        count+=1
于 2019-12-27T03:36:10.747 回答