从零开始的Python ACM Ch.6：质数与整数练习

孪生素数

问题描述
本节要研究孪生素数的问题，先来看看什么是孪生素数。
所谓孪生素数指的是间隔为2的两个相邻素数，因为它们之间的距离己经近得不能再近了，如同孪生兄弟一样，故将这一对素数称为孪生素数。
显然，最小的一对孪生素数是（1，3）。我们可以写出3、100以内的孪生素数，一共有8对，分别是（3，5），（5，7），（11，13），（17，19），（29，31)，（41，43），
（59，61)和（71，73）。随着数字的增大，孪生素数的分布也越来越稀疏，人工寻找孪生素数变得非常困难。
关于孪生素数还存在着一个著名的猜想一孪生素数猜想，即孪生素数是否有无穷多对，这是数论中还有待解决的一个重要问题。此处我们只讨论在有限范围内的孪生素数求解问题。
本节要解决的问题：编程求出3、1000以内的所有孪生素数。

其实很简单，直接遍历就好了

from math import sqrt

def isPrime(num):
    if num == 2: return True
    if num % 2 == 0: return False
    i = 3
    while i <= sqrt(num):
        if num % i == 0: return False
        i += 2
    return True

if __name__ == '__main__':
    flag = False
    primes = []
    primesset = []
    tmp = -1
    for i in range(1000):
        if isPrime(i) and not flag:
            primes.append(i)
            flag = True
            tmp = i
        elif isPrime(i) and flag:
            primes.append(i)
            primesset.append([tmp, i])
            tmp = -1
            flag = False
    print(primesset)

输出

[[1, 2], [3, 5], [7, 11], [13, 17], [19, 23], [29, 31], [37, 41], [43, 47], [53, 59], [61, 67], [71, 73], [79, 83], [89, 97], [101, 103], [107, 109], [113, 127], [131, 137], [139, 149], [151, 157], [163, 167], [173, 179], [181, 191], [193, 197], [199, 211], [223, 227], [229, 233], [239, 241], [251, 257], [263, 269], [271, 277], [281, 283], [293, 307], [311, 313], [317, 331], [337, 347], [349, 353], [359, 367], [373, 379], [383, 389], [397, 401], [409, 419], [421, 431], [433, 439], [443, 449], [457, 461], [463, 467], [479, 487], [491, 499], [503, 509], [521, 523], [541, 547], [557, 563], [569, 571], [577, 587], [593, 599], [601, 607], [613, 617], [619, 631], [641, 643], [647, 653], [659, 661], [673, 677], [683, 691], [701, 709], [719, 727], [733, 739], [743, 751], [757, 761], [769, 773], [787, 797], [809, 811], [821, 823], [827, 829], [839, 853], [857, 859], [863, 877], [881, 883], [887, 907], [911, 919], [929, 937], [941, 947], [953, 967], [971, 977], [983, 991]]

梅森素数

问题描述：梅森数（MersennePrime）指的是形如2n·1的正整数，其中指数n是素数，记为Mno如果一个梅森数是素数，则称其为梅森素数。例如2^2-1=3、2^3-1：7都是梅森素数。
当n：2、3、5、7时，Mn都是素数，但n=11时，Mn=2^11-1=2047=23×89，显然不是梅森素数。
1722年，瑞士数学大师欧拉证明了2^31-1=21474837是一个素数，它共有10位数，成为当时世界上己知的最大素数。
迄今为止，人们仅发现了47个梅森素数。梅森素数历来都是数论研究中的一项重要内容，也是当今科学探索中的热点和难点问题。
了解了梅森素数后，现在来看本节要解决的编程问题。
试求出指数n<20的所有梅森素数。

直接去算n在20以内质数的时候2^n-1是否为质数就行了

from math import sqrt


def isPrime(num):
    if num == 2:
        return True
    if num % 2 == 0:
        return False
    i = 3
    while i <= sqrt(num):
        if num % i == 0:
            return False
        i += 2
    return True


if __name__ == '__main__':
    flag = False
    primes = []
    result = []
    for i in range(20):  # 20以内的素数
        if isPrime(i):
            primes.append(i)
    for num in primes:
        if isPrime(2**num-1):
            result.append(2**num-1)
    print(primes, result)

输出

1	[1, 2, 3, 5, 7, 11, 13, 17, 19] [1, 3, 7, 31, 127, 8191, 131071, 524287]

回文数

问题描述：打印不超过n（n<256）的其平方具有对称性质的数

n = int(input('n: '))
result = []

for i in range(1,n+1):
    if str(i**2) == str(i**2)[::-1]:
        result.append(i)

print(result)

输出

1	[1, 2, 3, 11, 22, 26, 101, 111, 121, 202, 212]

水仙花数

问题描述：经典题目，三位数的数位上的数字的三次方等于数字本身

result = []
for i in range(100, 1000):
    a = str(i)[0]
    b = str(i)[1]
    c = str(i)[2]
    if int(a)**3 + int(b)**3 + int(c)**3 == i:
        result.append(i)

print(result)

输出

1	[153, 370, 371, 407]

阿姆斯特朗数

水仙花数的翻版，任意位数也可以有这个特性，求1000以内的这种数字

result = []
for i in range(0, 1001):
    if i < 10:
        if i**3 == i:
            result.append(i)
    elif i >= 10 and i < 100:
        a = str(i)[0]
        b = str(i)[1]
        if int(a)**3 + int(b)**3 == i:
            result.append(i)
    elif i >= 100 and i < 1000:
        a = str(i)[0]
        b = str(i)[1]
        c = str(i)[2]
        if int(a)**3 + int(b)**3 + int(c)**3 == i:
            result.append(i)
    elif i >= 1000:
        a = str(i)[0]
        b = str(i)[1]
        c = str(i)[2]
        d = str(i)[3]
        if int(a)**3 + int(b)**3 + int(c)**3 + int(d)**3 == i:
            result.append(i)

print(result)

输出

1	[0, 1, 153, 370, 371, 407]

完数

问题描述：一个数如果能由其因子相加得到，就称这个数字为完数。请输出1000以内的完数

from math import sqrt

result = []
for i in range(1, 1000):
    factor = []
    for j in range(1, int(i/2)+1):
        if i % j == 0: 
            factor.append(j)
            if sum(factor) == i: 
                result.append(i)
                break

print(result)

输出

1	[6, 24, 28, 496]

自守数

问题描述：一个数的平方的尾数等于自身的自然数即为自守数，求100 000以内的自守数

result = []
for i in range(100000):
    if str(i) == str(i**2)[-len(str(i)):]:
        result.append(i)

print(result)

输出

1	[0, 1, 5, 6, 25, 76, 376, 625, 9376, 90625]

高位数的高次方位数输出

题目描述：对于一个13位的高位数，进行13次方的运算后，输出最后三位数

num = input('num: ')

result = []
tmpnum = int(num[-3:])
last = 1
for i in range(13):
    last = int(str(last)[-3:]) * tmpnum

print(str(last)[-3:])

输入及输出

1 2	num: 1234567891234 504

不截断尾巴的实际数字为15477282471244379725868683797046205669901003401479261325193553207435375574886373743207123231086152401578649551681124388954385182017538129322035861770786709504

通过比较尾数发现做法是正确的