AcWing 算法基础课 数论

一、质数

  质数是大于1的自然数,只包含1和本身两个约数。

  1、质数的判定,O(sqrt(n))

    试除法,推荐循环i<=n/i(防止溢出和sqrt计算)

  2、分解质因子,O(logn~sqrt(n))

AcWing 算法基础课 数论
 1 for(int i=2;i<=n/i;i++)
 2 {
 3   if(n%i==0)
 4   {//此时2~i-1的质因子已经除完,i必为质数
 5         int s=0;
 6       while(n%i==0)
 7     {
 8 
 9      n/=i;
10      s++;
11     }
12             cout<<i<<s<<endl;
13   }
14 }
15 if(n!=1)
16     cout<<n<<1<<endl;//最后一个大于sqrt(n)的质因子
View Code

  3、筛法O(nloglogn)

    获得小于n的全部质数,思想为用全部数筛去后面的非质数

   (埃氏筛法可优化为仅用质数去筛质数的倍数,因为非质数一定有质因子,故只筛质数就可以全部筛掉)

    

AcWing 算法基础课 数论
 1 int primes[N];
 2 bool not_prime[N];
 3 int cnt = 0;
 4 void get_primes(int n)
 5 {
 6     for (int i = 2; i < n; i++)
 7     {
 8         if (!not_prime[i])
 9         {
10             primes[cnt++] = i;
11             for (int j = i + i; j <= n; j += i) not_prime[j] = true;
12         }
13 
14     }
15 
16 }
View Code

    (线性筛法可优化为,仅用当前数和前面的质数进行筛,筛到i%primes[j]==0,非质数会被第一个质因子筛掉)

 

      

AcWing 算法基础课 数论
 1 int primes[N];
 2 bool not_prime[N];
 3 int cnt = 0;
 4 void get_primes(int n)
 5 {
 6     for (int i = 2; i < n; i++)
 7     {
 8         if (!not_prime[i])
 9         {
10             primes[cnt++] = i;
11         }
12         for (int j = 0; primes[j] <= n / i; j++)
13         {
14             not_prime[primes[j]*i] = true;
15             if (i%primes[j] == 0) break;//primes[j]是primes[j]*i的最小质因子
16         }
17         
18 
19     }
20 
21 }
View Code

二、约数

  1、试除法求所有约数

  同试触法判断质数,O(sqrt(n))

  2、约数个数

  对全部质因数pi和次数ai,有约数个数为连乘Π(ai+1),(对每个pi,都有ai+1种取法)

  3、约数之和为连乘kΠ(求和i∑pk^ai)

  p^0+p^1+...+p^n

  =

  {

    t=1;

    for(n)

      t=t*p+1;

    return t;

  }

  5、辗转相除法(欧几里得算法)求最大公约数

  

AcWing 算法基础课 数论
1 int gcd(int a,int b)
2 {
3     return b ? gcd(b, a%b): a;
4 
5 }
View Code

 

上一篇:盘点 | 红利大年,人工智能加速数字化变革


下一篇:大凉山孩们穿上了AI辅助设计的新年新衣