数论与图论

数论🎈

筛质数

最普通的筛法O(nlogn)：

void get_primes2(){for(int i=2;i<=n;i++){if(!st[i]) primes[cnt++]=i;//把素数存起来for(int j=i;j<=n;j+=i){//不管是合数还是质数，都用来筛掉后面它的倍数st[j]=true;}}
}

诶氏筛法 O(nloglogn)：

void get_primes1(){for(int i=2;i<=n;i++){if(!st[i]){primes[cnt++]=i;for(int j=i;j<=n;j+=i) st[j]=true;//可以用质数就把所有的合数都筛掉；}}
}

线性筛O(n)

void get_primes(){//外层从2~n迭代，因为这毕竟算的是1~n中质数的个数，而不是某个数是不是质数的判定for(int i=2;i<=n;i++){if(!st[i]) primes[cnt++]=i;for(int j=0;primes[j]<=n/i;j++){//primes[j]<=n/i:变形一下得到——primes[j]*i<=n,把大于n的合数都筛了就//没啥意义了st[primes[j]*i]=true;//用最小质因子去筛合数//1)当i%primes[j]!=0时,说明此时遍历到的primes[j]不是i的质因子，那么只可能是此时的primes[j]<i的//最小质因子,所以primes[j]*i的最小质因子就是primes[j];//2)当有i%primes[j]==0时,说明i的最小质因子是primes[j],因此primes[j]*i的最小质因子也就应该是//prime[j]，之后接着用st[primes[j+1]*i]=true去筛合数时，就不是用最小质因子去更新了,因为i有最小//质因子primes[j]<primes[j+1],此时的primes[j+1]不是primes[j+1]*i的最小质因子，此时就应该//退出循环，避免之后重复进行筛选。if(i%primes[j]==0) break;}}}

试除法判断质数

输入n表示要判断的n个数，接下来输入n个数，判断其是否为质数

#include<bits/stdc++.h>
using namespace std;
int n;
bool isprime(long long a){if(a==1){return 0;}else if(a==2){return 1;}for(int i=2;i<=a/i;i++){//不要用开方或者i*i，开方函数较慢，i*i会越界if(a%i==0){return 0;}}return 1;
}
int main(){cin>>n;while(n--){long long a;cin>>a;if(isprime(a)) cout<<"Yes"<<endl;else cout<<"No"<<endl;}

分解质因数

解题思路：

• x 的质因子最多只包含一个大于 根号x 的质数。如果有两个，这两个因子的乘积就会大于 x，矛盾。
• i 从 2 遍历到 根号x。 用 x / i，如果余数为 0，则 i 是一个质因子。
• s 表示质因子 i 的指数，x /= i 为 0，则 s++， x = x / i 。
• 最后检查是否有大于 根号x 的质因子，如果有，输出。

#include <iostream>
#include <algorithm>using namespace std;void divide(int x)
{for (int i = 2; i <= x / i; i ++ )//i <= x / i:防止越界，速度大于 i < sqrt(x)if (x % i == 0)//i为底数{int s = 0;//s为指数while (x % i == 0) x /= i, s ++ ;cout << i << ' ' << s << endl;//输出}if (x > 1) cout << x << ' ' << 1 << endl;//如果x还有剩余，单独处理cout << endl;
}
{
int main()
{int n;cin >> n;while (n -- ){int x;cin >> x;divide(x);}return 0;
}