素数筛,线性筛(欧拉筛),莫比乌斯函数筛,前n个数的约数个数筛

问题：给出一个数n，输出1~n之间的素数

素数筛

1. 埃拉托斯特尼筛法

• 每次消去的倍数，直到没有可消的为止，剩下的数字则为素数；
  每次考虑消去的第一个数为,因为已经在为基数，为倍数的时候已经判断了;以此类推，当的倍数小于时都被判断了，于是只要判断的倍数大于等于的时候
  时间复杂度为；空间复杂度。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=1000+10;
int vis[M];
int cnt;
void getprim( )
{
   for(int i=2;i*i<=M;i++)
   {
       int k=i;
       for(int j=i*i;j<=M;j=i*k)
       {
           vis[j]=1;
           k++;
       }
   }
}
int main( )
{
   memset(vis,0,sizeof(vis));
   vis[1]=1;
   getprim( );
   for(int i=1;i<M;i++)
   {
       if(vis[i]==0)
       {
           cout<<i<<endl;
       }
   }
   return 0;
}

2. 欧拉筛法

• 在埃拉托斯特尼筛算法中有很多数都重复操作vis[j]=1,因为2的倍数如已经判断了，但是在4的倍数也有然后又判断一次所以就有重复的
  欧拉筛法
  每次用已筛出来的质数去筛更大的数，每个合数只被它最小的质因子筛掉。
  试想，如果2*6筛了12之后还没break，而是用3*6筛掉18，那么18还会被2*9筛一次，就重复了而根本原因就是6有2这个因子，而3*6筛掉的数一定也有2这个因子，3*6这个数应该被2这个因子筛掉，而不是3

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=1000+10;
int vis[M];
int prim[M];
int cnt;
void getprim( )
{
   memset(vis,0,sizeof(vis));
   memset(prim,0,sizeof(prim));
   for(int i=2;i<=M;i++)
   {
       if(!vis[i])//在2~i-1之间没有标记，意味着没有它的因数，那么它是质数
       {
           prim[cnt++]=i;
       }
       for(int j=0;j<cnt&&i*prim[j]<=M;j++)
       {
           vis[i*prim[j]]=1;//剔除每个质数的i倍的那个数
           if(i%prim[j]==0)//保证每个合数只被它最小的质因子剔除
           {
               break;
           }
       }
   }
}
int main( )
{
   cnt=0;
   getprim( );
   for(int i=0;i<cnt;i++)
   {
       cout<<prim[i]<<endl;
   }
   return 0;
}

问题：给出一个数n,输出1~n之间的每个数的欧拉函数

欧拉筛

• 根据欧拉函数的相关定理
  其中为质数
  其中互质

• 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=1000+10;
int vis[M];
int prim[M];
int phi[M];
int cnt;
void getprim( )
{
    memset(vis,0,sizeof(vis));
    memset(prim,0,sizeof(prim));
    memset(phi,0,sizeof(phi));
    phi[1]=1;
    for(int i=2;i<=M;i++)
    {
        if(!vis[i])
        {
            prim[cnt++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<cnt&&i*prim[j]<=M;j++)
        {
            vis[i*prim[j]]=1;
            if(i%prim[j]==0)
            {
                phi[i*prim[j]]=phi[i]*prim[j];
                break;
            }
            else
            {
                phi[i*prim[j]]=phi[i]*(prim[j]-1);
            }
            
        }
    }
}
int main( )
{
    cnt=0;
    getprim( );
    // for(int i=0;i<cnt;i++)
    // {
    //     cout<<prim[i]<<endl;
    // }
    // cout<<endl;
    for(int i=1;i<M;i++)
    {
        cout<<phi[i]<<endl;
    }
    return 0;i
}

• 意味着这个质数是的因子

因为
所以

因为分解出来的一定与分解出来的相同(其中的指数不一样)
所以

• 意味着与互质
  根据欧拉函数的积性函数
  

莫比乌斯函数筛

• μ(n) ——莫比乌斯函数，关于非平方数的质因子数目。
  

1）莫比乌斯函数μ(n)的定义域是N；
2）μ(1)=1；
3）当n存在平方因子时，μ(n)=0；
4）当n是素数或奇数个不同素数之积时，μ(n)=-1；
5）当n是偶数个不同素数之积时，μ(n)=1。

• 这个做起来比欧拉函数容易，在过程上，若为素数则，若，则，显然就是它的平方因子，否则,因为多了一个质因子

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=1e3+10;
int mob[M];
int prim[M];
int vis[M];
int cnt;
void getmob( )
{
    memset(vis,0,sizeof(vis));
    memset(prim,0,sizeof(prim));
    memset(mob,0,sizeof(mob));
    mob[1]=1;
    for(int i=2;i<M;i++)
    {
        if(!vis[i])//质数
        {
            prim[cnt++]=i;
            mob[i]=-1;//质数为-1
        }
        for(int j=0;j<cnt&&i*prim[j]<M;j++)
        {
            vis[i*prim[j]]=1;
            if(i%prim[j]==0)
            {
                mob[i*prim[j]]=0;//i%prim[j]==0,意味着i中有因子prim[j],所以i*prim[j]中有平方因子prim[j]
                break;
            }
            else
            {
                mob[i*prim[j]]=-mob[i];
            }
            
        }
    }
}
int main( )
{
    cnt=0;
    getmob( );
    for(int i=1;i<M;i++)
    {
        cout<<mob[i]<<endl;
    }
    return 0;
}

前n个数的约数个数筛

1. 一个大于的正整数都有一个唯一分解定理:
   (是质数)
2. 算术基本定理中，根据拆分后的质因子的指数，我们可以求出每个的约数的个数。所以的约数个数可以表示为:
   
3. 根据这个式子，我们可以用线性筛去筛出当前 N 的约数个数。
   筛的过程中，我们需要保存下最小质因子的个数。

证明:

首先规定：
表示的约数个数
表示的最小质因子的个数(指数)
表示第个质数

• 情况1：
  是一个质数,那么(约数为和自己本身)
  只有一个质因子就是自身 ,所以
• 情况2：
  时
  说明中没有这个质因子，但是有这个质因子，的唯一分解定理其中()
  所以
  
  所以
  所以
  那的最小质因子是什么呢！因为是从小到大枚举并且在线性筛中每个只会被自己最小的质因子剔除
  所以的最小质因子就是
  所以

情况3：
时
说明中有质因子,其中肯定是的最小质因子，因为是从小到大枚举

那么

所以

参考二连
「参考」 「参考」

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=1e3+10;
int d[M];
int prim[M];
int num[M];//i的最小质因子的个数(指数)
int vis[M];
int cnt;
void getd( )
{
    memset(vis,0,sizeof(vis));
    memset(prim,0,sizeof(prim));
    memset(d,0,sizeof(d));
    memset(num,0,sizeof(num));
    d[1]=1;
    for(int i=2;i<M;i++)
    {
        if(!vis[i])
        {
            prim[cnt++]=i;
            d[i]=2;
            num[i]=1;
        }
        for(int j=0;j<cnt&&i*prim[j]<M;j++)
        {
            vis[i*prim[j]]=1;
            if(i%prim[j]==0)
            {
                num[i*prim[j]]=num[i]+1;
                d[i*prim[j]]=d[i]/(num[i]+1)*(num[i*prim[j]]+1);
                break;
            }
            else
            {
                num[i*prim[j]]=1;
                d[i*prim[j]]=d[i]*2;
            }
        }
    }
}
int main( )
{
    cnt=0;
    getd( );
    for(int i=1;i<M;i++)
    {
        cout<<d[i]<<endl;
    }
    return 0;
}