Go教程

【Golang】输出100以内的素数

本文主要是介绍【Golang】输出100以内的素数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

一、任务要求

  输出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到\sqrt{}n均整除判断,时间复杂度O(\sqrt{}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

}

  

  

这篇关于【Golang】输出100以内的素数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!