使用Python查找第n个素数

Question

当我运行这段代码时，即使只计算到第十个素数(而不是1000)，我也会得到一个倾斜/加顶的输出--对于我的is_composite变量来说，所有的“非素数”标题，我的test_num给出的是素数和复合数，而我的prime_count是关闭的。

一些开发人员共享了使用函数和数学导入的答案--这是我们还没有讨论的问题。我并不是想得到最有效的答案；我只是试图编写可行的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 

Answer 1

请参阅麻省理工学院给您的作业提示。我引述如下：

1. 初始化一些状态变量
2. 将所有(奇数)整数>1生成为素数
3. 对于每个候选整数，测试它是否为素数。 3.1。一种简单的方法是测试是否有任何其他整数>1将候选数与0的余数均分。为此，您可以使用模块化算术，例如，表达式a%b除以整数a后返回余数。 3.2。您可能会考虑需要检查哪些整数作为除数--当然，您不需要超出正在检查的候选人的范围，但是，您多久才能停止检查？
4. 如果候选人是素数，则打印一些信息，以便知道自己在计算中的位置，并更新状态变量。
5. 当你到达适当的结束状态时停止。在制定这个条件时，不要忘记，您的程序没有生成第一个素数(2)。

看起来可能是这样的：

def primes(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#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]]

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向上迭代这些数字，检查它们是否是素数，如果它们是素数，则将它们添加到计数器中。当您到达1000停止并输出该数字时，将该数字传递给isprime函数。

当然还有其他更有效的方法，我个人更喜欢阿特金筛。但这将取决于你的实现，我的算法将服务于你的目的。

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

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

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.");}