使用Python找到第n个质数

Question

当我运行这段代码时，即使只计算前十个质数（而不是1000），我也会得到一个偏斜/失真的输出--我的is_composite变量所有的标题都是“not prime”，我的test_num给我质数和合数，而我的prime_count也有误。

一些开发人员分享的答案使用了函数和math导入--这是我们尚未涵盖的内容。我并不试图得到最有效的答案；我只是想编写可行的Python代码来理解循环的基础知识。

  # test a prime by diving number by previous sequence of number(s) (% == 0).  Do this by
  # counting up from 1 all the way to 1000.

test_num = 2 #these are the numbers that are being tested for primality
is_composite = 'not prime' # will be counted by prime_count
prime_count = 0 #count the number of primes


while (prime_count<10): #counts number primes and make sures that loop stops after the 1000th prime (here: I am just running it to the tenth for quick testing)


 test_num = test_num + 1   # starts with two, tested for primality and counted if so
 x = test_num - 1  #denominator for prime equation

 while (x>2):   
  if test_num%(x) == 0:
   is_composite = 'not prime'
  else: 
   prime_count = prime_count + 1 
  x = x - 1 


  print is_composite
  print test_num
  print prime_count 

- zkidd

---

具体是什么没有起作用？ - eldarerathis

你的算法速度较慢，可以使用数论进行优化。具体而言，只需检查小于或等于当前数字平方根的质数。 - alternative

离题：你代码中的一些注释是正确的，而另一些则很显然：“while x > 2: # runs while x is greater than 2” 是不言自明的。总体上：应该解释为什么（why），而不是做什么（what）。 - Adriano Varoli Piazza

你和我对于“大”质数有不同的想法。对我来说，一个大的质数是足够大，以至于所有小于该候选质数的质数所占用的内存（硬盘空间？）都比机器（集群？）可用的内存还多。对我来说，前大约2^40个质数都是“小”的。 - SingleNegationElimination

@zkidd：问题不在于作业的原因，而在于你的方法：如果你带着这个问题来并说“我已经做了这个和那个，但是我在这里遇到了这个问题”，那么这将表明你在付出努力后真正被难住了。而仅仅说“我有困难”，并且一开始的代码甚至没有一个打印语句，这显示出缺乏努力。 - Adriano Varoli Piazza

Answer 1

请参考MIT提供的提示进行作业：

1. 初始化一些状态变量

2. 将所有（奇数）大于1的整数生成为素数候选项

3. 对于每个候选整数，测试它是否是素数

   3.1. 一个简单的方法是测试是否有其他大于1的整数可以整除这个候选项并得到0余数。为此，您可以使用模运算，例如，表达式a％b返回将整数a除以整数b后的余数。

   3.2. 您可以考虑需要检查哪些整数作为除数 - 当然，您不需要超过您正在检查的候选项，但是您可以在什么时候停止检查？

4. 如果候选项是素数，则打印出一些信息以便您知道计算的进展，并更新状态变量

5. 当满足某些适当的结束条件时停止。在制定此条件时，请不要忘记您的程序没有生成第一个素数（2）。

它可能看起来像这样：

def primes(n):
    # https://dev59.com/snI95IYBdhLWcg3w-DH0#3035188
    """ Returns  a list of primes < n """
    sieve = [True] * n
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)
    return [2] + [i for i in xrange(3,n,2) if sieve[i]]

- Wok

---

昨天我浏览了那些提示，但是仍然有问题。因此我发帖询问。 - zkidd

尽管我已经查看了那些提示并重新观看了讲座，但我仍然感到很糟糕，因为我正在问这个问题。 - zkidd

你可能想要查看更高效的解决方案，以获取Pythonic的方式。 - Wok

Answer 2

首先，从您的素数检查算法的模糊描述中可以看出，您正在检查每个数字直到您测试质数的数字。然而，在现实中，您只需要测试到该数字的平方根。进一步的优化是除去所有偶数，除了二（您可以通过从一开始增加两个并单独测试2来实现这一点），最终得到以下代码：

def isprime(test):
    if test == 2: return True
    if test < 2 or test % 2 == 0: return False
    return not any(test % i == 0 for i in range(3, int(sqrt(test)) + 1, 2))

然后，您只需要迭代从2开始的数字，检查它们是否为质数，并在它们是质数时将计数器加1。当您达到1000时，请停止并输出传递给isprime函数的数字。

当然，还有其他更有效的方法，我个人更喜欢Atkin筛法。但是，实现该算法取决于您，我的算法将满足您的需求。

编辑：我注意到您的评论中提到“没有返回/发生任何事情”，这可能是由于您的算法效率低下造成的，如果您等待足够长的时间，您将得到一个答案。但是，我注意到您提供的代码中没有打印语句，我希望您运行的代码中有打印语句。

from math import sqrt

def isprime(test):
    if test == 2: return True
    if test < 2 or test % 2 == 0: return False
    return not any(test % i == 0 for i in range(3, int(sqrt(test)) + 1, 2))

test_num = 2
prime_count = 1

while (prime_count< 1000): 

 test_num = test_num + 1  

 if (isprime(test_num)):
     prime_count += 1

print test_num

- user461697

---

您不需要编写单独的 isprime 函数。您可以检查先前找到的质数整数作为当前整数的除数，因为您正在创建一个递增序列。 - Wok

例如，请查看rwh_primes(n)函数。 - Wok

我的算法只是一种替代方案，它可以以更低的效率实现相同的结果。如果zkidd想要了解，我提供了另一种Atkin筛法的替代方案。 - user461697

谢谢wok和njak32--我会查看所有内容。但现在我运行程序，它似乎要到“49”就停止了。我已经添加了我正在使用的打印语句。但是质数计数确实增加到了1000。你们两个可以检查一下上面的内容是否正确吗？ - zkidd

将prime_count初始化为1，因为您的当前方法中没有计算2。 - user461697

谢谢njak32！你的答案使用了math.import和def --- 我们还没有涵盖到这个，但我会使用你的输出来检查我的（不太有效率）输出。 - zkidd

Answer 3

这是我为C++编写的代码。但思维方式必须相同。

// This code was written by Mert Ener
#include <time.h>
#include <vector>
#include <iostream>

private: System::Void button1_Click_1(System::Object^  sender, 
                                          System::EventArgs^  e) { 
    using namespace std;
    UInt64 cloc = clock();
    long m = 1;
    long k = long::Parse(textBox1->Text)-2;   // The text you entered 
    std::vector<long> p(1,2);                 //   for the nth prime
    for( long n = 0; n <= k; n++ ) {
        m += 2;
        for( long l = 1; l <= n; l++ ) {
            if (m % p[l] == 0) {
                m += 2;
                l=0;}}
        p.push_back(m);}
    textBox2->Text = p[k+1].ToString(); // The textbox for the result.
    MessageBox::Show("It took me " + (clock() - cloc).ToString() 
                     + " milliseconds to find your prime.");}

- user2002000

Answer 4

以下代码生成了一个包含一百万以内的质数列表。 使用该列表，你可以以相对快速的方式测试小于一万亿的质数。 对于十到十二位的质数，这个代码运行时间非常快。

import math
from itertools import islice
# number of primes below the square root of x
# works well when x is large (x > 20 and much larger)
numchecks = lambda x: int((math.sqrt(x))/(math.log(math.sqrt(x)) - 1.084)) + 1

primes = [2,3,5]
primes = primes + [x for x in range(7, 48, 2) if all((x%y for y in islice( primes, 1, int(math.sqrt(x)) )))]
primes = primes + [x for x in range(49, 2400, 2) if all((x%y for y in islice( primes, 1, numchecks(x) )))]
primes = primes + [x for x in range(2401, 1000000, 2) if all((x%y for y in islice( primes, 1, numchecks(x) )))]

您可以通过扩展上述过程来增加保存的质数数量，但程序将需要很长时间（但仅需一次处理）。

在您的代码中，您可以使用以下方法测试“test_num”是否为质数...

test_num = 23527631
if test_num<100:
    checks = int(math.sqrt(test_num))
else:
    checks = numchecks(test_num)

isPrime = all(test_num%x for x in islice(primes, 0, checks))
print 'The number is', 'prime' if isPrime else 'not prime'
print 'Tested in', checks, 'divisions'

- Rajan

---

为什么不使用 isPrime = all(test_num % x for x in it.islice(primes, 0, checks))。islice 可能有点过头了，但是 all 是这里唯一的选择 ;) - aaronasterling

@Aaron：让它变得更快的方法！！谢谢。 - Rajan