leetcode中如何求素数
小编给大家分享一下leetcode中如何求素数,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!
成都创新互联专注于网站设计制作、成都网站建设、网页设计、网站制作、网站开发。公司秉持“客户至上,用心服务”的宗旨,从客户的利益和观点出发,让客户在网络营销中找到自己的驻足之地。尊重和关怀每一位客户,用严谨的态度对待客户,用专业的服务创造价值,成为客户值得信赖的朋友,为客户解除后顾之忧。
求1——n的素数的个数,有以下三种方法:
1,遍历法:
对于k(1 此方法的问题在于许多不必要的计算,因此可以想到用空间换时间:筛选出来的素数的倍数都可以标记为合数 2,埃氏筛法 欧拉筛法优化的一点就是改进了埃氏筛法的一点冗余:可以发现,在埃氏筛法中,我们对每一个n都标记了不止一次。比如10,当i=2时,10作为2的倍数被标记一次,当i=5时,10依然是5的倍数,又被多余的标记一次。 3,欧拉筛选法 欧拉筛法思想: 其基础是 “任何一个合数都可以由两个质数相乘得到” 。那么对于每一个n我们都可以用比它小的某一个质数来标记。 欧拉筛的难点就在于对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中如何求素数”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注创新互联行业资讯频道!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 }
func init(){prime:=make(map[int]bool) //prime[i]为flase表示i为质数//初始化,默认都是for(i:=2;i
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
本文标题:leetcode中如何求素数
网页URL:http://myzitong.com/article/jpphcg.html