四质数平方和 by YC
- 描述
-
早在16世纪，人们就开始研究将一个正整数表示为若干个正整数的平方和的问题。1621年，巴赫特（Bachet）提出：每一个正整数都可以表示为4个完全平方数之和。这一命题直到1772年，才由拉格朗日（Lagrange）第一个完整地给予证明，经历151年。
我们考虑这样一些正整数：它们不仅可以写成4个正整数的平方之和，还可以进一步写成4个质数的平方之和。即：X = p2+q2+r2+s2，其中p, q, r, s皆为质数。我们称这样的数为”四质数平方和“。
例如：1004 = 32 + 32 + 52 + 312 , 1023= 22 + 32 + 72 + 312
给定一个范围[m, n]，求所有满足m<=X<=n的四质数平方和X。
- 输入
- 一行中两个整数m和n，用空格分隔。(m<=n<=10000)
- 输出
- 在[m,n]范围内，所有四质数平方和，每个数一行。
- 样例输入
-
1000 1100
- 样例输出
-
1004 1012 1015 1018 1020 1023 1028 1036 1039 1044 1060 1063 1066 1068 1071 1076 1084 1087 1090 1092 1095 1100
- 提示
- 需要考虑程序的执行速度。简单地枚举四个整数并检查是否都是质数，需要花费很多时间。需要让每一个枚举的循环次数尽可能少。实际上，给定了最大数n后，能构成四质数平方和的质数其实是很有限的，它们的平方肯定要小于n。可以先找出这些质数，再基于这些质数进行枚举。
另外，Python中用幂运算计算平方（x**2），要比直接做乘法（x*x）耗时更多。
