素数

前置知识

小学数学知识

素数判定

小的直接试填法,大素数太麻烦了,遇到我再更,感兴趣的可以自行搜索Miller_Rabin素性测试

素数筛选

埃及筛

时间复杂度(nlog2log2n),解决1e7量级问题,内存占用约10mb

思路,从最小的素数开始一个个筛选(只要能被当前素数整除,就必定不是素数,直接删了),比如我们现在求1到13的素数,过程如下

(1)筛2:1,2,3,4,5,6,7,8,9,10,11,12,13

(2)筛3:1,2,3,4,5,6,7,8,9,10,11,12,13

(3)筛5:1,2,3,4,5,6,7,8,9,10,11,12,13

剩下的就是素数了,只要筛到sqrt(n)即可

int vis[n+1];//true为被筛
for(int i = 2; i <= n; i++) vis[i] = false;
for(int i = 2; i <= sqrt(n); i++){
    if(!vis[i]){
        for(int j = i*i; j <= n; j += i) vis[j] = true;
        //j从i*i开始也是优化,这样2为筛也可以防止2被筛,5为筛时,从25开始,10,15,20都已经在前面被筛过了
    }
}

欧拉筛

时间复杂度(n),解决1e8量级问题,内存占用约100mb

原理:一个合数只有一个最小的质因数,让每个合数只被它最小的质因数筛选一次,没有埃及筛的重复筛选

int prime[N];//记录素数
int vis[N];
int cnt = 0;
memset(prime, 0, sizeof(prime));
memset(vis, 0, sizeof(vis));
for(int i = 2; i <= n; i++){
    if(!vis[i]){
        prime[cnt++] = i;
    }
    for(int j = 0; j < cnt; j++){
        if(i * prime[j] > n) break;
        vis[i * prime[j]] = 1;
        if(i % prime[j] == 0) break;
    }
}

质因数分解

试除法

这里用来求解有多少个质因数

ll ans = 0;
for(ll i = 2; i <= sqrtl(x); i++){
    if(x % i == 0){
        ans++;
        while(x % i == 0) x /= i;
    }
}
 if(x > 1) ans++;
cout<<ans;

欧拉筛

只要改一下vis定义就可以了,用来求1到n每个数的最小质因数

int prime[N];//记录素数
int vis[N]; //记录每个数的最小质因数
int cnt = 0;
memset(prime, 0, sizeof(prime));
memset(vis, 0, sizeof(vis));
for(int i = 2; i <= n; i++){
    if(!vis[i]){
        prime[cnt++] = i;
        vis[i] = i;
    }
    for(int j = 0; j < cnt; j++){
        if(i * prime[j] > n) break;
        vis[i * prime[j]] = prime[j];
        if(i % prime[j] == 0) break;
    }
}