小编给大家分享一下leetcode中如何求素数，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！
求1——n的素数的个数，有以下三种方法：
1，遍历法：
对于k（1<k<=n）;判断k 是否可以被 2到sqrt（k）的整数整除
func isprime(x int) bool{ if x<=1{ return false } for(i:=2;i<=sqrt(x+0.5);i++){//+0.5是为了防止精度误差 if x%i==0{ return false } } return true }
此方法的问题在于许多不必要的计算，因此可以想到用空间换时间:筛选出来的素数的倍数都可以标记为合数
2，埃氏筛法
func init(){prime:=make(map[int]bool) //prime[i]为flase表示i为质数//初始化,默认都是for(i:=2;i<maxn;i++){ if !prime[i]{ for j:=2*i;j<maxn;j+=i){//把所有i的倍数都进行标记 prime[j]=true; } } }}
欧拉筛法优化的一点就是改进了埃氏筛法的一点冗余：可以发现，在埃氏筛法中，我们对每一个n都标记了不止一次。比如10，当i=2时，10作为2的倍数被标记一次，当i=5时，10依然是5的倍数，又被多余的标记一次。
3,欧拉筛选法
欧拉筛法思想：
其基础是 “任何一个合数都可以由两个质数相乘得到” 。那么对于每一个n我们都可以用比它小的某一个质数来标记。
func prime(n int)int{ m:=make([]int,n) p:=make([]int,n) count:=0 for i:=2;i<=n;i++{ if m[i-1]==0{ // 如果未被筛过，则为素数 p[count]=i count++ } for j:=0;j<count;j++{ if i*p[j]>n{ break } m[i * p[j]-1] = 1; // 将已经记录的素数的倍数进行标记 if i % p[j] == 0{ //关键步骤 break } } } fmt.Println(count) return count}
欧拉筛的难点就在于对if (i % prime[j] == 0)这步的理解，当i是prime[j]的整数倍时，记 m = i / prime[j]，那么 i * prime[j+1] 就可以变为 (m * prime[j+1]) * prime[j]，这说明 i * prime[j+1] 是 prime[j] 的整数倍，不需要再进行标记(在之后会被 prime[j] * 某个数 标记)，对于 prime[j+2] 及之后的素数同理，直接跳出循环，这样就保证了每个合数都是被它的最小因子筛去的，避免了重复标记。
以上是“leetcode中如何求素数”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注亿速云行业资讯频道！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
