今日笔记---数论
1、质数的判定---试除法
质数判定的条件：
1）n>1; 2)n是否只包含1和本身两个约数
最优写法，时间复杂度是O(sqrt(n))。
#include
using namespace std;
bool is_prime(int n)
{if(n<2) return false;for(int i=2;i<=n/i;i++){if(n%i==0) return false;}return true;
}int main()
{int n;cin>>n;cout< 之前写法的缺点：
1)for(int i=2;i 2）for(int i=2;i 3)for(int i=2;i*i<=n;i++) //此时i*i有溢出的风险，可能会超过整数的范围 思路：从小到大枚举所有小于sqrt(n)的质因子，并在(n%i==0)成立时，将n中的i模尽。 时间复杂度：O(logn--sqrt(n))，近似认为是O（sqrt(n)） 结论1：n中最多只包含一个大于sqrt(n)的质因子 补充知识：两个没有共同质因子的正整数称为互质。因为1没有质因子，1与任何正整数（包括1本身）都是互质。 （1）朴素筛法求素数个数： 思路：从小到大（即2--n）开始枚举，记录下当前没被标记过的数，然后依次在序列中把当前i的倍数标记上。所以剩下的没被标记过数就是质数。 时间复杂度为O(nlogn) (2)埃式筛法： 优化：仅在当前数是质数的时候，开始从此标记其倍数。因为如果这个数不是质数，那么按照（1）的做法在此前就已经将这个数及这个数的倍数标记过了，按照(1)的方法会在进行一趟无用功，所以做此优化。 时间复杂度是O(n log logn) (3)线性筛法： 思路：把每一个合数用他的质因子筛掉，核心：每个数n只会被其最小质因子筛掉。 第二个for(；pj<=n/i；)！ 和埃氏筛法的区别：线性筛是站在当前枚举到的 合数 i 的角度，是质数就加入p[], 同时将素数数组元素和i进行乘积组合，将可乘出来的结果标记上，直到素数数组元素为i的最小质因子退出进行组合的这个for。本质上每个数都是被自身的最小质因子筛掉的；（我的理解，像是随着i开展局部探索，把附近能被筛掉的数筛掉。每个数都只有一个最小质因子，且最小质因子只有一个，所以每个数都只会被筛一次） 埃氏筛法：站在质因子的角度，把1--n中质因子为当前数的数字筛掉. 两种情况： 1）i%p[j]==0 说明p[j]是i的最小质因子 2）i%p[j]!=0 说明p[j]一定小于i的所有质因子 三种筛法的速度对比：由上到下对应(3)--(1)2、分解质因数---试除法
#include 3、筛质数
#include #include #include 
上一篇：对比学习论文综述
下一篇：【zookeeper】命令行