Python 完美数

Question

所以我应该编写一个 Python 程序来识别并打印某个闭区间 [ 2, n ] 中的所有完美数字，每行一个。我们只需要使用嵌套的 while 循环/ if-else 语句。我以某种方式使用 for 循环完成了它，但无法使用 while 循环找出相同的结果。如果您能告诉我如何将我的代码转换为 while 循环，我将不胜感激。多谢你们。这是我所拥有的：

 limit = int(input("enter upper limit for perfect number search: "))

for n in range(2, limit + 1):
    sum = 0
    for divisor in range(1, n):
        if not n % divisor:
            sum += divisor
        if sum == n:
            print(n, "is a perfect number")

原文由 Joe 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

这应该工作：

 limit = int(input("enter upper limit for perfect number search: "))

n = 1

while n <= limit:

    sum = 0
    divisor = 1
    while divisor < n:
        if not n % divisor:
            sum += divisor
        divisor = divisor + 1
    if sum == n:
        print(n, "is a perfect number")
    n = n + 1

原文由 Mark Skelton 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

这是一个（更有效的）筛子版本：

 # search all numbers in [2..limit] for perfect numbers
# (ones whose proper divisors sum to the number)
limit = int(input("enter upper limit for perfect number search: "))

# initialize - all entries are multiples of 1
#   (ignore sieve[0] and sieve[1])
sieve = [1] * (limit + 1)

n = 2
while n <= limit:
    # check n
    if sieve[n] == n:
        print(n, "is a perfect number")
    # add n to all k * n where k > 1
    kn = 2 * n
    while kn <= limit:
        sieve[kn] += n
        kn += n
    n += 1

---

运行到 10000 次发现

6 is a perfect number
28 is a perfect number
496 is a perfect number
8128 is a perfect number

分解这些显示出一个有趣的模式：

 6          3 * 2                         (  4 - 1) * (  4 / 2)
28         7 * 2 * 2                     (  8 - 1) * (  8 / 2)
496       31 * 2 * 2 * 2 * 2             ( 32 - 1) * ( 32 / 2)
8128     127 * 2 * 2 * 2 * 2 * 2 * 2     (128 - 1) * (128 / 2)

其中第一个因数 (3, 7, 31, 127) 是一个小于二的幂的质数，它乘以二的相同幂的一半。 Also, the powers involved are prime ( 2**2 , 2**3 , 2**5 , 2**7 ).

事实上，欧几里德证明了 (2**p - 1) * 2**(p - 1) 是一个完美的数字，如果 p 2**p - 1 是素数，这只有在 —b75b66f433668d0b4dab93fbb-5-5630 是素数时才有可能（尽管不确定）欧拉走得更远，证明了所有甚至完美的数字都必须是这种形式。

这表明一个 非常 高效的版本——我将继续使用 for 循环，请随意重写它。首先，我们需要素数来源和 is_prime 测试：

 def primes(known_primes=[7, 11, 13, 17, 19, 23, 29]):
    """
    Generate every prime number in ascending order
    """
    # 2, 3, 5 wheel
    yield from (2, 3, 5)
    yield from known_primes
    # The first time the generator runs, known_primes
    #   contains all primes such that  5 < p < 2 * 3 * 5
    # After each wheel cycle the list of known primes
    #   will be added to.
    # We need to figure out where to continue from,
    #   which is the next multiple of 30 higher than
    #   the last known_prime:
    base = 30 * (known_primes[-1] // 30 + 1)
    new_primes = []
    while True:
        # offs is chosen so  30*i + offs cannot be a multiple of 2, 3, or 5
        for offs in (1, 7, 11, 13, 17, 19, 23, 29):
            k = base + offs    # next prime candidate
            for p in known_primes:
                if not k % p:
                    # found a factor - not prime
                    break
                elif p*p > k:
                    # no smaller prime factors - found a new prime
                    new_primes.append(k)
                    break
        if new_primes:
            yield from new_primes
            known_primes.extend(new_primes)
            new_primes = []
        base += 30

def is_prime(n):
    for p in primes():
        if not n % p:
            # found a factor - not prime
            return False
        elif p * p > n:
            # no factors found - is prime
            return True

然后搜索看起来像

# search all numbers in [2..limit] for perfect numbers
# (ones whose proper divisors sum to the number)
limit = int(input("enter upper limit for perfect number search: "))

for p in primes():
    pp = 2**p
    perfect = (pp - 1) * (pp // 2)
    if perfect > limit:
        break
    elif is_prime(pp - 1):
        print(perfect, "is a perfect number")

哪个发现

enter upper limit for perfect number search: 2500000000000000000
6 is a perfect number
28 is a perfect number
496 is a perfect number
8128 is a perfect number
33550336 is a perfect number
8589869056 is a perfect number
137438691328 is a perfect number
2305843008139952128 is a perfect number

一秒钟之内 ;-)

原文由 Hugh Bothwell 发布，翻译遵循 CC BY-SA 3.0 许可协议