输入10个整数判断是否是素数代码（给定一个非负整数c）
2021-05-04：给定一个非负整数c，你要判断是否存在两个整数a和b，使得a*a b*b=c。【举例】c=5时，返回true。c=4时，返回true。c=3时，返回false。
福大大 答案2021-05-04：
四平方和定理。时间复杂度：O(sqrt(N))。空间复杂度：O(1)。
1.n一直除以4，直到不能整除为止。
2.n%8,如果余7，直接返回4。
3.从1到sqrt(n)开始循环，a*a b*b=c成立时，a和b都不为0，返回2;a和b有一个为0，返回1。
4.返回3。
5.在本题中，返回值是1和2的是true。返回值是3和4的是false。
代码用golang编写。代码如下：
package main
import (
"fmt"
"math"
)
func main() {
for i := 1000; i <= 1100; i {
ret := isSquares(i)
fmt.Println(i, ret)
}
}
//4 1 1 1
func isSquares(n int) bool {
return numSquares(n) <= 2
}
func numSquares(n int) int {
for n&3 == 0 { //n%4==0
n >>= 2 //n/=4
}
if n&7 == 7 { //n%8==7
return 4
}
a := 0
for a*a <= n {
b := int(math.Sqrt(float64(n - a*a)))
if a > b {
break
}
if a*a b*b == n {
ret := 0
if a != 0 {
ret
}
if b != 0 {
ret
}
return ret
}
a = 1
}
return 3
}
执行结果如下：
免责声明：本文仅代表文章作者的个人观点，与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺，请读者仅作参考，并自行核实相关内容。文章投诉邮箱：anhduc.ph@yahoo.com
