首页
学习
活动
专区
圈层
工具
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

素数的筛法

素数的筛法有很多种 在此给出常见的三种方法 以下给出的所有代码均已通过这里的测试 埃拉托斯特尼筛法 名字好长 :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

    筛法求质数

    筛法求质数 给定一个正整数 n,请你求出 1∼n 中质数的个数。 输入格式 共一行,包含整数 n。 输出格式 共一行,包含一个整数,表示 1∼n 中质数的个数。...数据范围 1≤n≤106 输入样例: 8 输出样例: 4 讲解: 筛法求质数是一种很快速的,在一个范围内求质数的方法,他的原理在,在一个[2,n]的范围内,我们设置一个boolean数组,标记每个数字...,最开始默认他们都是质数,为false,然后我们通过筛法把不是质数的位置标记为true。...筛法的原理就是,如果一个数字是质数,那么这个数字a,他的倍数一定不是质数,所以可以看见这循环语句for (int j = i + i; j <= n; j += i) st[j] = true; 把质数...输入样例: 8 3 1 3 -1 -3 5 3 6 7 输出样例: -1 -3 -3 -3 3 3 3 3 5 5 6 7 提交代码 C++ #include using

    4510
    领券