试除法判定质数O(sqrt(n))
质数
在大于1的整数中, 只包含1和本身两个约数, 就叫做质数
性质1:如果 d 是 n 的约数, 那么 n/d 也是 n 的约数
可以只枚举每对中较小的那个
for(int i = 2; i <= sqrt(n * 1.0); i++);
// 不推荐, 因为每次都要算 sqrt
for(int i = 2; i * i <= n; i++)
// 不推荐, 当n特别大时, ixi 可能溢出
for(int i = 2; i <= n / i; i++)
// 推荐
分解质因数O(最大sqrt(n))
定义: 把一个合数分解成若干个质因数的乘积的形式
根据算术基本定理,不考虑排列顺序的情况下,每个正整数都能够以唯一的方式表示成它的质因数的乘积。
n=p1^a1 * p2^a2 *p3^a3.....pn^an
求一个数分解质因数,要从最小的质数除起,一直除到结果为质数为止。
且只会出现一个 大于 sqrt(n) 的质因数。
从2开始枚举数, 每遇到一个质因数, 即 n % i == 0
且 i 为质数的数
就一直进行 n /= i 直到 i不再是n的因数
这样便是从小到大分解质因数
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int main()
{
cin >> n;
while(n--)
{
int x;
cin >> x;
for(int i = 2; i <= x / i; i++)
{
if(x % i == 0)
{
int s= 0;
while(x % i == 0)
{
x /= i;
s++;
}
cout << i << " " << s << endl;
}
}
if(x > 1) cout << x << " " << 1 << endl;
cout << endl;
}
return 0;
}
筛质数
从2 到 n 每碰见一个质数就把他所有的倍数删去, 这样当遇到一个数 i 时, 1-i 中不存在 i的约数, 故 i 就是质数
这就是埃氏筛:O(nloglogn)
bool st[N];
int prime[N], cnt;
for(int i = 2; i <= n;i ++)
{
if(!st[i])
{
prime[cnt++] = i;
for(int j = i + i; j <= n; j += i)
st[j] = true;
}
}
线性筛:
for(int i = 2; i <= n; i++)
{
if(!st[i]) prime[cnt++] = i;
for(int j = 0; prime[j] < n / i; j++)
{
st[prime[j] * i] = true;
if(i % prime[j] == 0) break;
}
}
n只会被它的最小质因子筛掉
1. i % prime[j] == 0
prime[j]
一定是i的最小质因子, prime[j]
一定是 i * prime[j]
的最小质因子
2. i % prime[j] != 0
说明 prime[j]
一定小于 i 的所有质因子, 也一定是 i * prime[j]
的最小质因子
对于一个合数x, 在枚举到x之前肯定会枚举到最小质因子, 故筛掉, 且每个合数只会被筛一次