输出100以内的质数,并将质数求和,每行显示5个质数
质数:(质数prime number)定义为在大于1的自然数中,除了1和它本身以外不再有其他因数,质数有无穷多个。
因为质数只能被1和自己整除,所以要输出100以内质数,最简单粗暴的方式就是用除数X,被除数2 ~ (X-1)之间求余,如余数有为0,则X不是质数。用count记录余数为0的次数,用sum统计所有质数之和,用times记录每行已经输出质数的次数,times为0则输出换行 指令,然后重新赋值次数。
package main import ( "fmt" ) func main() { var times = 5 var sum int for i := 2; i <= 100; i++ { var count int for j := 2; j <= i-1; j++ { if i%j == 0 { count++ } } if count == 0 { fmt.Printf("%v ", i) times-- sum += i } if times == 0 { fmt.Println() times = 5 } } fmt.Printf("质数之和为:%v", sum) } //输出结果为: //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 //质数之和为:1060
开根号法:从2到n均整除判断,时间复杂度O(n)(原因:素数是因子为1和本身, 如果数c不是素数,则还有其他因子,其中的因子,假如为a,b.其中必有一个大于sqrt(c) ,一个小于sqrt(c) 。所以m必有一个小于或等于其平方根的因数,那么验证素数时就只需要验证到其平方根就可以了。即一个合数一定含有小于它平方根的质因子。
package main import ( "fmt" "math" ) func main() { var times = 5 var sum int for i := 2; i <= 100; i++ { var count int for j := 2; j <= int(math.Floor(math.Sqrt(float64(i)))); j++ { if i%j == 0 { count++ } } if count == 0 { fmt.Printf("%v ", i) times-- sum += i } if times == 0 { fmt.Println() times = 5 } } fmt.Printf("质数之和为:%v", sum) //输出结果: //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 //质数之和为:1060 }