1.最大质因数
13195的所有质因数为5、7、13和29。
600851475143最大的质因数是多少？
解题思路：
本题有2种实现方式：
- 找出这个数的所有质因数，再找出其中最大的那一个；
- 不断递归调用，判断每次得到的数是否为质数，如果不是，则继续查找。
代码如下：
def max_prime1(num): '''普通方法''' prime = 1 temp = num while temp > 1: num_root = int(pow(num, 0.5)) for i in range(2, num_root+1): if temp % i == 0: temp /= i if i > prime: prime = i break return prime def max_prime2(num): '''递归方法''' if num == 1: return 1 for i in range(2, int(pow(num, 0.5))+1): if num % i == 0: return max_prime2(num // i) return num print(max_prime1(600851475143)) print(max_prime2(600851475143))
输出：
6857 6857
性能分析：
第2种方法的性能更高，因为第2种方法相对于第1种，遍历的次数更少。
2.最大回文乘积
回文数就是从前往后和从后往前读都一样的数。由两个2位数相乘得到的最大回文乘积是 9009 = 91 × 99。找出由两个3位数相乘得到的最大回文乘积。
解答思路：
本题也有2种解答方式，两种方式均需要判断一个数是否是回文数，区别在于处理三位数因数的方式：
单层循环，从999*999开始，一直往下找，找到第一个为两个三位数乘积并且为回文数的数即为所找的数；
双层循环，内外循环都从999开始，找到内层与外层的乘积为回文数的数，再找出其中最大的数，即为结果。
代码如下：
def is_three_multi(num): '''判断一个数是否是两个三位数的乘积''' is_multi = False for j in range(100, int(pow(num, 0.5)+1)): if num % j == 0 and num // j < 1000 and num // j >= 100: is_multi = True break return is_multi def is_palindrome(num): '''判断一个数是否是回文数''' is_palin = False num_str = str(num) str_len = len(num_str) half_len = str_len // 2 for k in range(half_len): if num_str[k] != num_str[str_len-1-k]: break else: is_palin = True return is_palin def max_palindrome_multiply1(): '''单层循环方法''' for i in range(999*999, 100*100-1, -1): if is_three_multi(i): if is_palindrome(i): return i return None print(max_palindrome_multiply1()) def is_palindrome(num): '''判断一个数是否是回文数''' is_palin = False nums = [] while num > 0: nums.append(num % 10) num //= 10 num_len = len(nums) for i in range(num_len//2): if nums[i] != nums[num_len - 1 - i]: break else: is_palin = True return is_palin def max_palindrome_multiply2(): '''双层循环方法''' max_pro = 1 for i in range(999, 99, -1): for j in range(999, 99, -1): pro = i * j if pro > max_pro and is_palindrome(pro): max_pro = pro break return max_pro print(max_palindrome_multiply2())
输出：
906609 906609
性能分析：
经过测试，两种方法的效率相近。
3.最小倍数
2520是最小的能够被1到10整除的数。
最小的能够被1到20整除的正数是多少？
解题思路：
本题有3种实现方式：
本题求最小的能够被1到20整除的正数，其实就是求1到20的最小公倍数，1到n的最小公倍数也是n*(n-1)的倍数，通过不断判断n*(n-1)的倍数是否都能被1到n整除，如果能整除则这个数就是寻找的答案。
从1开始累乘，如果当前的数与乘积互质、则乘这个数，否则乘这个数与这个数乘积的最大公因数的商。
先找出2-20所有的质数，并得到它们的乘积作为初始值S，剩下的全是非质数，对于每一个非质数找出组成这个非质数的最小质数z，如果这个非质数能整除S，则S不变，否则S乘z
代码如下：
import sys def min_cumulative_number1(n): max_int = sys.maxsize base = n * (n - 1) min_cumul = 1 for i in range(1, max_int): min_cumul = base * i for j in range(1, n + 1): if min_cumul % j != 0: break if j == n: return min_cumul return min_cumul print(min_cumulative_number1(20)) def max_common_divider(m, n): '''寻找两个数的最大公因数''' if m < n: m, n = n, m while n != 0: m, n = n, m % n return m def min_cumulative_number2(n): res = 1 for i in range(1, n + 1): common_divider = max_common_divider(res, i) if common_divider == 1: res *= i else: res *= (i // common_divider) return res print(min_cumulative_number2(20)) def is_prime(n): '''判断一个数是否是质数''' is_prime = True for i in range(2, int(pow(n, 0.5)) + 1): if n % i == 0: is_prime = False break return is_prime def min_prime(n): '''寻找一个数的最小质数''' res = 1 for i in range(2, int(pow(n, 0.5)) + 1): if n % i == 0: res = i break return res def get_primes(n): '''获取前n个数中的素数列表''' primes = [] for i in range(2, n + 1): if is_prime(i): primes.append(i) return primes def min_cumulative_number3(n): nums = [i for i in range(2, n + 1)] res = 1 prime_list = get_primes(n) for num in prime_list: res *= num nums.remove(num) for num in nums: res = res if res % num == 0 else res * min_prime(num) return res print(min_cumulative_number3(20))
输出：
232792560 232792560 232792560
性能分析：
其中第一种方式的性能较低，因为要循环的次数太多（sys.maxsize表示Python中最大的整数）；
第二种和第三种的性能相近。
4.并非盈数之和
完全数是指真因数之和等于自身的那些数。例如，28的真因数之和为1 + 2 + 4 + 7 + 14 = 28，因此28是一个完全数。
一个数n被称为亏数，如果它的真因数之和小于n；反之则被称为盈数。
由于12是最小的盈数，它的真因数之和为1 + 2 + 3 + 4 + 6 = 16，所以最小的能够表示成两个盈数之和的数是24。
通过数学分析可以得出，所有大于28123的数都可以被写成两个盈数的和；
尽管我们知道最大的不能被写成两个盈数的和的数要小于这个值，但这是通过分析所能得到的最好上界。
找出所有不能被写成两个盈数之和的正整数，并求它们的和。
解题思路：
1.寻找所有的盈数，再找出不能写成两个数的和的数，判断和的方式为嵌套循环，时间复杂度较高；
2.判断一个数是否是盈数、形成盈数的列表，在找不能由两个盈数的和组成的数时，用到的是二分法，复杂度降低。
代码如下：
def find_num_fac_sum(n): '''寻找一个数的真因数之和''' fac_sum = 0 for i in range(1, n // 2 + 1): if n % i == 0: fac_sum += i return fac_sum def find_more_nums(n): '''找到前n个数的所有盈数''' more_nums = [] for j in range(1, n + 1): if find_num_fac_sum(j) > j: more_nums.append(j) return more_nums def not_sum(n, nums): '''判断一个数是否能写成两个盈数之和''' not_exists = True for k in nums: if n - k in nums: not_exists = False break return not_exists def find_no_more_sum_numbers1(): more_nums = find_more_nums(28123) sum_res = 0 for i in range(1, 28124): if not_sum(i, more_nums): sum_res += i return sum_res print(find_no_more_sum_numbers1()) def is_abundant(n): '''判断一个数是否是盈数''' fac_sum = 0 for i in range(1, n // 2 + 1): if n % i == 0: fac_sum += i return fac_sum > n def find_no_more_sum_numbers2(): abu_list = [] for i in range(1, 28124): if is_abundant(i): abu_list.append(i) non_abu_sum = 0 abu_list_len = len(abu_list) for j in range(1, 28124): non_abu = True begin = 0 end = abu_list_len - 1 # 二分法判断 while begin <= end: two_sum = abu_list[begin] + abu_list[end] if two_sum > j: end -= 1 elif two_sum < j: begin += 1 else: non_abu = False break if non_abu: non_abu_sum += j return non_abu_sum print(find_no_more_sum_numbers2())
输出：
4179871 4179871
性能分析：
很明显，第二种方法的性能更高。
5.第10001个素数
列出前6个素数，它们分别是2、3、5、7、11和13。
我们可以看出，第6个素数是13。
第10,001个素数是多少？
解题思路：
有2种方法，区别主要在于判断素数的思路，一种是直接判断，另外一种是判断是否是大于2的偶数，如果是则不需要再循环判断，否则才需要循环判断，显然，第二种方法效率会相对高一些，因为循环的次数更少了。
代码如下：
def prime1(n): '''判断一个数是否是素数''' is_prime = True for i in range(2, int(pow(n, 0.5)) + 1): if n % i == 0: is_prime = False break return is_prime def n_prime1(n): count = 0 i = 1 while count < n: i += 1 if prime(i): count += 1 return i print(n_prime1(10001)) def prime2(n): '''判断一个数是否是素数''' is_prime = True if n < 2: is_prime = False elif n == 2: pass else: # 偶数 if n & 1 == 0: is_prime = False # 奇数 else: for i in range(3, int(pow(n, 0.5)) + 1, 2): if n % i == 0: is_prime = False break return is_prime def n_prime2(n): import sys count = 0 for i in range(2, sys.maxsize): if prime2(i): count += 1 if count == n: return i print(n_prime2(10001))
输出：
104743 104743
性能分析：
一般情况下，第二种方法的效率更高。
