质数笔记

一：关于质数

大于1

只包含1和其本身两个因数

二：

1：质数的判定：试除法

2：分解质因数：试除法

直接算的话，复杂度O(n)

优化：(1)性质：n中最多只包含一个大于sqrt(n)的质因子，咋直接枚举到sqrt(n)即可。最后加个特判，如果n>1，算一个因子。

适用于n<=2e9

#include <bits/stdc++.h>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn = 1e3+10;
//vector<int>g[maxn];
void _get(ll n)
{
    for(int i=2;i<=n/i;i++)
    {
        if(n%i==0)
        {
            int cnt=0;
            while(n%i==0)
            {
                n=n/i;
                cnt++;
            }
            cout<<i<<" "<<cnt<<endl;
        }
    }
    if(n>1)
        cout<<n<<" "<<1<<endl;
    cout<<endl;    
}
int main(){
    int t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        _get(n);
        
    }
}

3：筛素数

1：最最普通的筛，对于一个素数i，每次由它往后标记掉j+=i

复杂度：n*Iogn

void _get(ll n)
{
    memset(st,false,sizeof(st)); 

    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            pr[cnt++]=i;
        }
        for(int j=i+i;j<=n;j+=i)
        {
            st[j]=true;
        }
    }
}

2：优化上述

只筛质数的倍数，大概可以快三倍左右

    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            pr[cnt++]=i;
            for(int j=i+i;j<=n;j+=i)
            {
                st[j]=true;
            }            
        }
    }

3：埃氏筛法(O(nloglogn))

整数的唯一分解定理：任何一个大于1的自然数 N，如果N不为质数，都可以唯一分解成有限个质数的乘积

    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            pr[cnt++]=i;
            for(int j=i+i;j<=n;j+=i)
            {
                st[j]=true;
            }            
        }
    }

4：线性筛（欧拉筛法）(O(n))

是在埃氏筛法的基础上，让每一个合数，只被它的最小质因子筛选一次，避免重复筛。

关于 i % pr[j]==0 break;

如果i%pr[j]==0,那么i==pr[j]*k

如果接着标记，那么就有st[pr[j+1]*i]=true;

而i*pr[j+1]==pr[j+1]*k*pr[j]==x，即以后的循环中，如果i==pr[j]*k，x还会被筛一次。

void init()
{
    memset(st,false,sizeof(st));
    for(int i=2;i<maxn;i++)
    {
        if(!st[i])
            pr[cnt++]=i;
        for(int j=0;pr[j]*i<maxn&&j<cnt;j++)
        {
            st[pr[j]*i]=true;    
            if(i%pr[j]==0)    //欧拉筛的关键，防止重复筛，保证合数只被其最小的素因子筛一次 
            { 
                break;
            }                
        }
    }
}