首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    素数

    素数有很多种 在此给出常见的三种方法 以下给出的所有代码均已通过这里的测试 埃拉托斯特尼 名字好长 :joy:  不过代码很短 思路非常简单,对于每一个素数,枚举它的倍数,它的倍数一定不是素数...看来这种算法还是不够优秀 下面我们来探索一下他的优化 另外,这种算法的时间复杂度:$O(n*logn)$ 埃拉托斯特尼优化版 根据唯一分解定理 每一个数都可以被分解成素数乘积的形式 那我们枚举的时候...欧拉 我们思考一下第二种的运算过程 不难发现,对于6这个数,它被2了一次,又被3了一次 第二次显然是多余的, 我们考虑去掉这步运算 1 #include 2 #include...,那么两个素数的乘积一定没有被过,可以避免重复 当i不是素数的时候 程序中有一句非常关键的话 1 if(i%prime[j]==0) break; 这句话可以保证:本次循环只能出不大于 的数...时间复杂度:严格 总结 在一般情况下,第二种已经完全够用。 第三种的优势不仅仅在于速度快,而且还能够积性函数,像欧拉函数,莫比乌斯函数等。 这个我以后还会讲的

    1.3K60

    客户端基本不用的算法系列:素数

    Eratosthenes Eratosthenes 进行的是打表,也就是平时说的离线操作,当查询量比较大的时候,我们往往采用这种方法进行离线操作处理;该算法的内容是:首先假设 n 个数全部都是素数...欧拉 - 线性 回忆一下,在我们的暴力算法中,为了简化计算,我们只对小于等于 sqrt(n) 的数进行取余检查;这里可以采取类似但是更简洁的办法,只要保证每个合数只会被他的最小素因子掉就可以了,...复杂度对比 Eratosthenes 的时间复杂度理论值是 O(N loglogN) ,而线性的理论复杂度是 O(N) 。...可是我通过实际的时间统计,发现 Eratosthenes 更快且更稳定(一脸黑人问号)??...,只要使用 Eratosthenes 就可以解决我们 80% 的问题。

    1.7K10

    Python|欧拉求质数

    这个时候就可以使用来求质数,本文介绍的是欧拉。其运用的原理是质数的倍数一定不是质数。因此将质数的倍数直接标记成合数,以达到筛选质数的目的。...同样以此为思路的还有埃氏,但埃氏具有缺陷:对于一个合数,有可能被多次,例如20 = 2*10 = 4*5。...而对此进行改进,用合数的最小质因子进行筛选来确保每个合数只被筛选一次,这就是欧拉。 但是具体是怎么做到每个合数只被筛选一次,我们来看下面的代码。...例如:i=2筛选4,i=3筛选6和9,但到i=4的时候,prime先为2,掉8,但运行到I % prime == 0这一步的时候就直接break了,也就避免了再遍历prime = 3的时候掉12,而...12是由i = 6时,prime = 2时掉。

    1.6K20
    领券