go实现求质数个数

Go （质数个数）

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

Go语言实现代码思路

• 方法一（简单遍历）
  从2到n的质数，n对从2到（n-1）进行整除操作
  1. 设置一个flag默认为true，若能被整除，则不是质数，flag变为false，跳出循环
  2. 定义一个计数器，每一次flag为true则+1

func countPrimes(n int) int {//质数：质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。count:=0  //定义一个count用作计数for i:=2;i<n;i++{  //范围从2：n开始进行循环flag:=true      //默认flag设置为truefor j:=2;j<=int(math.Sqrt(float64(i)));j++{   //j的值不用设置到i，只用到根号i，注意使用sqrt需要转换为float还要转回到intif i%j==0{flag=false //能被整除则不是质数break      //跳出循环}}if flag{count+=1   //是质数则计数器+1}}return count    //返回值}

其实j的值不用循环到n，只用循环到根号n，需要使用到math的sqrt的函数，需要将n转换为float64的类型，转换完了需要再转回int
方法一因为遍历太多，所以要超时。

• 方法二（厄拉多塞筛法）
  
  厄拉多塞筛法：先将2-N的数放入表中，在2上面画圈（没有划掉），划掉所有2的倍数，然后表中第一个没有画圈也没有被划掉的数是3，又对3画圈，将3的倍数划掉。以此类推，直到≤N。此时，被画了圈的数就都是质数。

代码实现思路：

1. 定义一个空数组，并将0-n中所有数添加到数组中
2. 开始进行嵌套循环，里面的j循环负责将圈到的数据的倍数进行标记为1，i负责累加值
3. 遍历数组，数组中值有不为1的值，计数器则+1

func countPrimes(n int) int{count:=0          //定义计数器var array []int   //定义空数组for i:=0;i<n;i++{ //在空数组中添加值array=append(array,i)}for i:=2;i*i<n;i++{        //进行遍历for j:=i*i;j<n;j=j+i{  //将i的倍数设置标记为1array[j]=1}}for i:=2;i<n;i++{         //遍历数组if(array[i]!=1){      //如果数组内不为1 ，计数器加1count++}}return count}