使用 Python 查找第 n 个素数 [英] Finding the nth prime number using Python
问题描述
当我运行这段代码时，即使只是数到第 10 个质数(而不是 1000)，我也会得到一个倾斜/顶升的输出——我的 is_composite 变量的所有非质数"标题，我的 test_num 给了我质数合数，而我的 prime_count 已关闭
When I run this code, even for just counting to the 10th prime number (instead of 1000) I get a skewed/jacked output--all "not prime" titles for my is_composite variable, my test_num is giving me prime and composite numbers, and my prime_count is off
开发人员共享使用函数和数学导入的一些答案--这是我们尚未涵盖的内容.我不是想得到最有效的答案；我只是想编写可行的 python 代码来理解循环的基础知识.
Some of the answers that developers have shared use functions and the math import--that's something we haven't yet covered. I am not trying to get the most efficient answer; I am just trying to write workable python code to understand the basics of looping.
# 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
推荐答案
查看 MIT 用于您的作业.我在下面引用它们:
See the hints given by MIT for your assignment. I quote them below:
初始化一些状态变量
Initialize some state variables
生成所有(奇数)整数 > 1 作为质数的候选
Generate all (odd) integers > 1 as candidates to be prime
对于每个候选整数，测试它是否是素数
For each candidate integer, test whether it is prime
3.1.一种简单的方法是测试是否有任何其他大于 1 的整数将候选者平均除以 0 余数.为此，您可以使用模算术，例如，表达式 a%b 返回整数 a 除以整数 b 后的余数.
3.1. One easy way to do this is to test whether any other integer > 1 evenly divides the candidate with 0 remainder. To do this, you can use modular arithmetic, for example, the expression a%b returns the remainder after dividing the integer a by the integer b.
3.2.您可能会考虑需要检查哪些整数作为除数 - 当然您不需要超出您正在检查的候选人，但是您可以多快停止检查?
3.2. You might think about which integers you need to check as divisors – certainly you don’t need to go beyond the candidate you are checking, but how much sooner can you stop checking?
如果候选人是素数，打印出一些信息，这样你就知道你在计算中的位置，并更新状态变量
If the candidate is prime, print out some information so you know where you are in the computation, and update the state variables
当您达到某个适当的结束条件时停止.在制定此条件时，不要忘记您的程序没有生成第一个素数 (2).
Stop when you reach some appropriate end condition. In formulating this condition, don’t forget that your program did not generate the first prime (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]]
这篇关于使用 Python 查找第 n 个素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
