Python算法：数论问题 |
您所在的位置：网站首页 › python完数的算法 › Python算法：数论问题 |
|
目录 完全数 水仙花数 素数 回文素数 平方回文数 分解质因数 最大公约数 最小公倍数 Stein 算法求最大公约数 小结 数论是研究整数及其性质的数学学科。在数论中，研究的对象主要是整数、质数、素数、约数、同余、模运算等基本概念和性质。数论的问题简单而又充满了智慧，本文将探讨一些基本的数论问题和算法。 完全数完全数指的是一个正整数，它的所有因子之和等于它本身，而因子不包括该数本身。一个数的因子就是所有可以整除这个数的数，而不包括该数本身。可以通过完全数的定义来编写查找完全数的算法。计算一个数的所有因子之和，判断与其是否相等。 目前并没有找到一种高效的方法来直接计算任意大数是否为完全数。已知的完全数非常稀少，而且它们的规律并不明确。随着数字的增大，它的因子数量也随之增多，计算过程会变得更加耗时，越往后查找完全数的速度越慢。为避免造成“程序失去响应”的误会，本案例会输出当前正在判断的数字，并且覆盖已经输出的非完全数。 # 判断一个数是否完全数，如果是完全数，返回因子列表 def perfect_number(number): factor_sum = 0 factors = [] # 从 1 开始，逐个判断是否是 number 的因子，不包括 number 自身 for num in range(1, number): # 如果 num 是 number 的因子，则累加，并将 num 加入因子列表 if number % num == 0: factor_sum += num if factor_sum > number: # 如果因子之和已经大于 number，说明 number 不是完全数，直接返回 return False, [] factors.append(num) # 上面的代码可以使用列表推导式简化，为了方便理解，这里不使用列表推导式 # factors = [num for num in range(1, number // 2 + 1) if number % num == 0] # factor_sum = sum(factors) if factor_sum == number: # 如果因子之和等于 num，则 num 是完全数，同时返回因子列表 return True, factors else: # 否则，num 不是完全数，同时返回空列表 return False, [] n = int(input("请输入一个正整数 n：")) print("小于 %d 的完全数有：" % n) for i in range(1, n): # 覆盖输出，不换行 print("\r%d" % i, end="") # 判断 i 是否是完全数，如果是，则输出完全数及其因子 is_perfect, pn = perfect_number(i) if is_perfect: print(" = ", end="") # 用 + 号连接完全数的因子 print(" + ".join(map(str, pn))) # 输出 n 的宽度个空格，覆盖最后一个非完数的输出 print("\r%s" % " " * len(str(n)), end="") 水仙花数水仙花数（也称为自恋数、自幂数）指的是一个 n 位的正整数（n>=3），它的每个数字的 n 次幂之和等于它本身。 from math import log10 # 判断一个数是否水仙花数 def narcissus_number(num): factor_sum = 0 temp = num # 求 num 的位数 num_len = int(log10(num)) + 1 # 计算 num 的各位数字的 n 次方和 while temp > 0: # 取出 temp 的个位数字 digit = temp % 10 # 累加 digit 的 n 次方 factor_sum += digit ** num_len # 去掉 temp 的个位数字 temp //= 10 return factor_sum == num n = int(input("请输入一个正整数 n：")) print("小于 %d 的水仙花数有：" % n) for i in range(100, n): if narcissus_number(i): print(i, end=" ") 素数素数又称质数，指在一个大于 1 的自然数中，除了 1 和此自然数自身外，无法被其它自然数整除的数。素数的分布没有明显的规律，一般根据素数的定义来分析数值不大的数是否为素数。 # 判断一个数是否素数 def is_prime_number(number): # 素数定义为大于 1 的自然数，所以小于等于 1 的数都不是素数 if number 0: # 将 reverse 左移一位，然后加上 num 的个位数字 reverse = reverse * 10 + num % 10 # 去掉 n 的个位数字 num //= 10 return number == reverse # 判断一个数是否素数 def is_prime_number(number): # 素数定义为大于 1 的自然数，所以小于等于 1 的数都不是素数 if number 0: # 将 reverse 左移一位，然后加上 num 的个位数字 reverse = reverse * 10 + num % 10 # 去掉 n 的个位数字 num //= 10 return number == reverse n = int(input("请输入一个正整数 n：")) print("小于 %d 的平方回文数有：" % n) for i in range(1, int(sqrt(n))): if is_palindrome(i * i): print("%d = %d * %d" % (i * i, i, i)) 分解质因数分解质因数是指将一个合数分解成若干个质数的乘积的过程。合数是指在大于 1 的整数中除了能被 1 和本身整除外，还能被其他数整除的数。质数即前面提到的素数，是只能被 1 和自身整除的正整数。分解质因数的过程可以用试除法实现，具体步骤如下： 1. 从 2 开始，依次尝试将待分解的数除以 2，如果可以整除，则将 2 作为一个质因子，继续将商分解成质因数； 2. 如果商不可以被 2 整除，则尝试将其除以 3，如果可以整除，则将 3 作为一个质因子，继续将商分解成质因数； 3. 依此类推，直到商为 1，分解过程结束。 # 分解质因数 def factorize(number): factors = [] i, num = 2, number while num > 1: # 如果能被整除，则 i 是 n 的质因子 if num % i == 0: factors.append(i) # 去掉 n 的因子 i num //= i else: i += 1 return factors n = int(input("请输入一个正整数 n：")) # 输出 n 的质因数，质因数之间用 * 号连接 print("%d = " % n, end="") print(" * ".join(map(str, factorize(n)))) 最大公约数最大公约数是指两个或多个整数的公共因数中最大的一个。可以用辗转相除法来求两个数的最大公约数。已知两自然数 m、n，辗转相除法求最大公约数执行过程如下： 1. 计算 m 除以 n 的余数 r； 2. 如果 r==0，则 n 为求得的最大公约数，否则执行下一步； 3. 将 n 的值保存到 ｍ 中，将 r 的值保存到 n 中，重复执行步骤 1 和 2，直到 r==0 得到最大公约数。 上述过程可以通过递归来实现： 1. 如果 n 是 0，则 m 是最大公约数； 2. 递归调用计算 n 和 r（即 m % n）两数的最大公约数。 由于是取模运算，m 和 n 谁大谁小没有关系，如果 m b: m, n = a, b else: m, n = b, a # 如果其中一个数为0，另一个数就是它们的最大公约数 if n == 0: return m # 如果两个数都是偶数，则公约数是 m/2 和 n/2 的最大公约数的两倍 if m & 1 == 0 and n & 1 == 0: return 2 * gcd_stein(m // 2, n // 2) # 如果 m 是偶数，n 是奇数，则公约数是 m 的一半和 n 的最大公约数 if m & 1 == 0: return gcd_stein(m // 2, n) # 如果 m 是奇数，n 是偶数，则公约数是 m 和 n 的一半的最大公约数 if n & 1 == 0: return gcd_stein(m, n // 2) # 如果两个数都是奇数，则公约数是 (m+n)/2 和 (m-n)/2 的最大公约数 return gcd_stein((m + n) >> 1, (m - n) >> 1) # 输入两个正整数，以空格分隔 str1, str2 = input("请输入两个正整数：").split() num1, num2 = int(str1), int(str2) print("它们的最大公约数是： %d" % gcd_stein(num1, num2)) 小结 当探索数论问题时，我们遇到了许多有趣的概念和算法。我们了解了完全数、水仙花数、回文素数、平方回文数等等。我们还学习了一些常见的数论算法，如分解质因数、最大公约数、最小公倍数等。 数论作为数学的一个分支，不仅令人着迷，而且具有广泛的应用。它在密码学、编码理论、计算机科学等领域起着重要的作用。通过深入研究数论问题，我们能够培养出抽象思维、逻辑推理和问题解决能力。 希望本文对读者有所启发，增加对数论问题的兴趣和理解。数论世界广阔而精彩，还有许多有待探索的领域和问题。无论是学术研究还是日常生活中的应用，数论都是一个充满挑战和奇妙的领域，值得我们深入探索。祝愿大家在数论的世界中找到乐趣，并不断拓展自己的知识和思维。 |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |