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

素数

素数法有很多种 在此给出常见的三种方法 以下给出的所有代码均已通过这里的测试 埃拉托斯特尼法 名字好长 :joy:  不过代码很短 思路非常简单,对于每一个素数,枚举它的倍数,它的倍数一定不是素数...这样一定可以保证每个素数都会被出来 还有,我们第一层循环枚举到 就好,因为如果当前枚举的数大于n,那么它能出来的数一定在之前就被枚举过 比如说: 不难发现我们从20枚举所去的数一定被...看来这种算法还是不够优秀 下面我们来探索一下他的优化 另外,这种算法的时间复杂度:$O(n*logn)$ 埃拉托斯特尼法优化版 根据唯一分解定理 每一个数都可以被分解成素数乘积的形式 那我们枚举的时候...,只有在当前数是素数的情况下,才继续枚举就好 这样可以保证每个素数都会被出来 1 #include 2 #include 3 using namespace std...,那么两个素数的乘积一定没有被过,可以避免重复 当i不是素数的时候 程序中有一句非常关键的话 1 if(i%prime[j]==0) break; 这句话可以保证:本次循环只能出不大于 的数

1.3K60

线性素数(探索中的不断优化)

工欲善其事必先利其器 首先素数是什么? 素数就是一个数除了1和他本身没有其他因数的数叫做质数。 合数即为对立概念 当然,1既不是素数也不是合数 素因子是什么?...由欧拉函数得到结论: 每一个合数都可以写成几个素数相乘的形式, 这些素数即为该合数的质因子 我们的目的是建立一张素数表 范围可达1~1e8左右 以bool数组存放,是素数为true 否则为false...(埃氏)O(nloglogn) 接近线性但不是 基本思想:找到一个素数,不断倍增,得到的数一定不是素数去。...上面的小程功能是找出1~n素数个数 v5.0欧拉线性 O(n) 埃氏的缺点很明显 :对于一个合数,有可能被多次。...因为欧拉法的原理便是通过最小素因子来消除。

56720
领券