数论基础 2025.2.10

1 .质数筛 是否为质数

质数-若一个正整数无法被除了1和它自身之外的任何自然数整除，则称该数为 质数(prime)

否则称该正整数为 合数(Composite number)

1. 试除法(定义)

     patr A
     bool Is_Prime(int x){
     if(x<2) return 0;
     for(int i=2;i<=x-1;i++)
         if(x%i==0) return 0;
     return 1;
    }
    part B
    bool Is_Prime(int x){
    if(x<2) return 0;
    for(int i=2;i*i<=x;i++)
        if(x%i==0) return 0;
     return 1;
    }
   

   一个数如果有因数，一定是一个大于一个效应 或者就是所以只要枚举1~

   2.埃氏筛oioioioio

   每个质数的倍数就是合数

    bool Check[];
    void Get_Prime(int n)//1~n{
        for(int i=2;i<=n;i++)
          if(!Check[i]){
            for(int j=2;i*j<=n;j++)
                Check[i*j]=1;
         }
    }
   

   3 .线性筛

   埃氏筛会重复标记 12—既是3的倍数也是2的倍数

   所以线性筛！首先，任意一个合数都可以被分解成一个质数和一个数的积。对于任意一个合数，我们用“这个合数 = 最小质因数 × 最大因数(非自己)”，来表示

   bool Is_Prime[];
   int Prime[],top=0;
   void Get_Prime(int n){
         for(int i=2;i<=n;i++){
             if(!Is_Prime[i]) Prime[++top]=i;
             for(int j=1;i<=Prime[j]*i<=n&&j<=Top;j++){
                 Is_Prime[i*Prime[j]]=1;
                 if(i%Prime[j]==0) break;
             }
         }
   }  
   

2.欧拉函数(Euler's totient function) 欧拉

,若的最大公因数为1，即 互质

就是1~n中与n互质的数的个数

将n分解质因数可得

• [推导]

• 把分解质因数后这些质因数在1~n中的倍数就是不能对产生贡献的数，举个粒子： 那么在中 2 ，3 ，5 的倍数就无法与300互质1-300中有个2的倍数，有个3的倍数，有个5的倍数

  

  同理 6 既是2的倍数也是3的倍数

  10 既是2的倍数也是5的倍数

  15 既是5的倍数也是3的倍数

  这些数每个被减了两遍所以要加回来

  1-300中有个6的倍数......

  所以这么多个数与300不互质

  转化一下

  

  然后因式分解

  

  !

  再来一个？？

  

  ！！！

  int Got_Phi(int x){//找x的欧拉值
      int ans=x;//初始认为全与x互质 
      for(int i=2;i*i<=x;i++){
          if(x%i==0){//i是x的因数
            ans=ans*((i-1)/i);//如公式
            while(x%i==0) x/=i;//把次方剔除
          }
       }
      if(x>1) ans=ans*((x-1)/x);//x自己是质数
      return ans;
  }