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")

Answer 1

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

# 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) 是一个小于 2 的幂的素数，然后乘以相同的 2 的幂的一半。此外，所涉及的权力是质数 ( 2**2, 2**3, 2**5, 2**7)。

事实上，欧几里得证明(2**p - 1) * 2**(p - 1)了如果2**p - 1是素数，它是一个完美数，这只有在是素数时才有可能（虽然不能确定）p。欧拉更进一步，证明了所有甚至完全数都必须具有这种形式。

这表明了一个非常有效的版本 - 我将继续使用 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

不到一秒钟;-)

Answer 2

您可以将for循环替换为以下内容：

n = 2
while n < limit + 1:
   ...
   divisor = 1
   while divisor < n:
      ...
      divisor += 1
   ...
   n += 1

提示：您也可以将其n/2用作第二个循环的上限，因为的任何除数n都不能大于n/2。

Answer 3

这应该有效：

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