1

我正在尝试为埃拉托色尼筛子编写一个 python 脚本。我已经完成了所有工作，但是当我告诉程序测试每个数字是否是 √ 输入下方的至少一个素数的倍数时。它运行良好，但是当我尝试删除一个倍数时，它一直有效，直到它尝试删除 6 两次......我一直在查看我的代码，但似乎无法找出原因。我对 Python 很陌生，所以非常感谢您的帮助！--- 请注意，由于 SOF 制作代码块的方式，我的代码间距已关闭：

import math, os, threading

global iswhole
global tdprime

def iswhole(x):
if x%1 == 0:
    return True
else:
    return False

def tdprime(x):
prime = True
n = 2

while n < x:
    if iswhole(x/n) == True:
        return False
        prime = False
        n = x
    else:
        n += 1

if prime == True:
    return True

number = 0

while number != 1:

number = int(input("Enter number to calculate all primes up to:  "))
number_range = range(1,number+1)
sqrt = math.sqrt(number)
rsqrt = round(sqrt)
thelist = []
tsl = []

for num in range(1,rsqrt):
    if tdprime(num) == True:
        tsl.append(num)
tsl.remove(1)

for x in number_range: ## Making the List
    thelist.append(x)
    ## Note it's " Key: Value " in dictionaries

print(tsl)
print("thelist: ",thelist)
print("Square root of input = ",sqrt)
print("Rounded Square root of input = ",rsqrt)
print()

for x in thelist: ## Testing each number in thelist

    multiple = False

    for y in tsl: ## Each prime number under √number

        if iswhole(x/y):
            print(x) ## If the current number in thelist divided by one of the prime numbers under √number is a whole
            thelist.remove(x)## Remove the current number which isn't a prime
            thelist.sort()
            multiple = True ## Make multiple true so it doesn't print (could remove the multiple stuff and other if function, kind of pointless function now)

    if multiple == False:
        print("Prime! ",x)


print(thelist)
4

3 回答 3

2

您的代码可以通过以下实现大大简化：

  • 可以根据需要轻松生成最多n的数字，它们不必预先计算并存储在列表中。

  • 2 是唯一的偶数，所以你只需要测试奇数。

  • 所有数字都可以唯一地完全分解为素数（这称为算术基本定理）。这意味着您需要尝试除以的唯一数字是您之前计算的素数——所有其他数字无论如何都可以被这些素数中的至少一个整除（或者它们本身就是素数）。

尝试以下方式：

stop = int(input("Enter number to calculate all primes up to: "))

primes = []

for n in range(3, stop, 2): # Step by two each time
    was_prime = True # Needed to break out of nested loop
    for p in primes:
        if n % p == 0: # A prime divides n
             was_prime = False
             break # No need to continue
    if was_prime:
        primes.append(n)

print(primes) # You can insert the number 2 here if you like

另外，请注意间距和缩进。在 Python 中，当您的间距错误时，不仅难以阅读，而且会出现运行时错误。

于 2011-12-14T02:05:59.520 回答
1

我看到这个位有问题：

for x in thelist: ## Testing each number in thelist

    multiple = False

    for y in tsl: ## Each prime number under √number

        if iswhole(x/y):
            print(x) ## If the current number in thelist divided by one of the prime numbers under √number is a whole
            thelist.remove(x)## Remove the current number which isn't a prime
            thelist.sort()

您在迭代时调用thelist.remove(x)and 。您通常不想修改您在 Python 中迭代的结构。它通常会混淆执行迭代的内部机制；你会得到一些症状，比如神秘地跳过元素或处理它们两次，或者其他奇怪的东西。thelist.sort()thelist

于 2011-12-14T04:42:31.560 回答
1

我有点担心你的iswhole()功能：

def iswhole(x):
    if x%1 == 0:
        return True
    else:
        return False

（顺便说一句，这可以简单地重写return (x%1 == 0)并跳过return True和return False部分。）

浮点数是奇数：

>>> 10.0%1
0.0
>>> (10.1 * 10)%1
0.0
>>> (10.01 * 100)%1
0.0
>>> (10.001 * 1000)%1
0.0
>>> (10.0001 * 10000)%1
0.0
>>> (10.00001 * 100000)%1
0.0
>>> (10.000001 * 1000000)%1
0.0
>>> (10.0000001 * 10000000)%1
0.0
>>> (10.00000001 * 100000000)%1
1.1920928955078125e-07

对于诸如 的输入6，这似乎不是问题，但对于较大的输入，它可能会成为问题。比较浮点数很麻烦。

对于这个6问题，我想建议您不要使用可变列表来跟踪您的数据，而应该使用数组来代替。数组永远不需要排序（事实上你sort()的程序中有 a 有点像试图掩盖某种错误）并且从列表中间删除元素通常非常昂贵。（这sort几乎意味着你的性能无论如何都会变差。对于小输入来说没什么大不了的，但尝试以 1000000 作为起点。）将数组中的元素设置为1or0几乎总是比可变列表便宜得多。

于 2011-12-14T01:59:09.863 回答