一、质数
质数是大于1的自然数,只包含1和本身两个约数。
1、质数的判定,O(sqrt(n))
试除法,推荐循环i<=n/i(防止溢出和sqrt计算)
2、分解质因子,O(logn~sqrt(n))
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的全部质数,思想为用全部数筛去后面的非质数
(埃氏筛法可优化为仅用质数去筛质数的倍数,因为非质数一定有质因子,故只筛质数就可以全部筛掉)
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,非质数会被第一个质因子筛掉)
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、辗转相除法(欧几里得算法)求最大公约数
1 int gcd(int a,int b) 2 { 3 return b ? gcd(b, a%b): a; 4 5 }View Code