有名设计网站,务川自治县建设局网站,微信管理平台,做ppt网站动态本文用于个人算法竞赛学习#xff0c;仅供参考 目录 一.质数的判定
二.分解质因数
三.质数筛
1.朴素筛法 2.埃氏筛法
3.线性筛法 四.约数
1.求一个数的所有约数
2.约数个数和约数之和
3.欧几里得算法#xff08;辗转相除法#xff09;-- 求最大公约数 一.质数的判定 … 本文用于个人算法竞赛学习仅供参考 目录 一.质数的判定
二.分解质因数
三.质数筛
1.朴素筛法 2.埃氏筛法
3.线性筛法 四.约数
1.求一个数的所有约数
2.约数个数和约数之和
3.欧几里得算法辗转相除法-- 求最大公约数 一.质数的判定
质数质数是指在大于1的自然数中除了1和它本身以外不再有其他因数的数。常见的质数有2, 3, 5, 7, 11等。质数也被称为素数。
试除法时间复杂度On^ 1/2 bool is_prime(int n)
{if (n 2)return false;for (int i 2; i n / i; i) //如果存在 a ÷ b c , 那么就有 a ÷ c b; {if (n % i 0){return false;}}return true;
}
二.分解质因数 试除法时间复杂度On^ 1/2
//存放分解后质数的个数
unordered_mapint, int primes;void divide(int n)
{//从2开始试除for (int i 2; i n / i; i)// i^2 n{//合数进不来因为被前面的质数约去了if (n % i 0){while (n % i 0){primes[i];n / i;}}}if (n 1)primes[n];
}int main()
{divide(84);for (auto prime: primes){cout prime.first : prime.second endl;}return 0;
}
三.质数筛
问题给定一个n筛出2~n的所有质数
1.朴素筛法
假设一个数n它的因数有a 那么n的因数a一定小于n所以只需要通过a的倍数就能筛掉n所以朴素筛法就是从2到n筛掉它们的倍数最后剩下的就是质数。
时间复杂度N(1 1/2 1/3 ... 1/n) N*lnN, O(N*lnN); 可以发现同一个数可能会被筛掉多次当样本个数非常多的时候是非常浪费时间的要如何优化降低对一个数筛的次数呢 2.埃氏筛法
埃氏筛法是对上面朴素筛法的优化只筛掉质数的倍数来减少筛掉同一个数的次数。
埃氏筛法Sieve of Eratosthenes是一种用来找出一定范围内所有素数的算法。其基本思想是从2开始不断地将质数的倍数标记为非质数最终剩下的即为质数。 筛掉4的倍数时其实在筛掉2的倍数时就筛掉了因为4是2的倍数4的倍数也是2的倍数所以4就没必要再去筛掉它的倍数了对于一个合数总会有它的质数代替它来筛掉它的倍数。
质数定理指出小于给定数n的质数个数约为 n / ln(n)。
优化后时间ON*loglogN
const int N 100;
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉void get_primes(int n)
{for (int i 2; i n; i){if (st[i]) continue;primes[cnt] i;for (int j i i; j n; j i)st[j] true;}
}我们发现还是存在对同一个数多次筛掉的情况如12被2和3筛掉两次还能再优化吗
3.线性筛法
线性筛法是一种在O(n)的复杂度情况下筛选出2~n的所有质数。 它的原理是从2开始每次找到一个最小的质数然后把它的倍数都标记为非质数即每个数合数只会被它的最小质因数筛掉。
比如上面的埃氏筛法12会被2和3筛两次线性筛法只会通过12的最小的质数2来筛掉。 最外层for循环遍历2~nprimes保存2~i的质数内层for循环从小枚举质数 1.对于 primes[j] n / i; 如果i是合数会走到 if (i % primes[j] 0) break 结束掉 如果i是质数会走到 primes[j] i 后结束掉 所以不用担心存在越界问题 2.对于 if (i % primes[j] 0) break; 若 i % primes[j] ! 0, primes[j]一定小于i的最小质因子primes[j] 一定是primes[j] * i 的最小质因子因为primes从小到大枚举且primes[j] 小于i 若i % primes[j] 0,primes[j] 一定是i的最小质因子primes[j] 一定是primes[j] * i 的最小质因子因为primes从小到大枚举且primes[j] 小于i 如果i % primes[j] 0,就应该break了为什么 已知i % primes[j] 0,就说明i是合数i已经再前面通过k * primes[j] 筛掉了 假设我们没有break走到primes[j 1], 会有 i * primes[j 1], 代入得 k * primes[j] * primes[j 1],很明显primes[j] primes[j 1], 说明一个数已经被primes[j] 筛掉过了再通过primes[j]筛就重复了。 3.对于每一个合数x一定会被筛掉假设x的最小质因子为p当i 遍历到x / p时x一定会被筛掉。 4.每一个合数都会被它的最小质数筛掉说明每个数只会被筛一次所以是线性的时间复杂度是On。 int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉void get_primes(int n)
{for (int i 2; i n; i ){if (!st[i]) primes[cnt ] i;for (int j 0; primes[j] n / i; j ){st[primes[j] * i] true;if (i % primes[j] 0) break;}}
} 四.约数
1.求一个数的所有约数
试除法枚举 i n / i, 看i 是否是约数
vectorint get_divisors(int n)
{vectorint result;for (int i 2; i n / i; i){if (n % i 0){result.push_back(i);//避免加入同一个数if (n / i ! i)result.push_back(n / i);}}sort(result.begin(), result.end());return result;
}
2.约数个数和约数之和
给定一个数N求N的约数个数
将N进行质因数分解p有N p1^c1 * p2^c2 * ... *pk^ck
对于每个质数pc可以取0~c则约数个数 (c1 1) * (c2 1) * ... * (ck 1)
约数之和 (p1^0 p1^1 ... p1^c1) * ... * (pk^0 pk^1 ... pk^ck) 思路
由N p1^c1 * p2^c2 * ... *pk^ck约数和为(p1^0 p1^1 ... p1^c1) * ... * (pk^0 pk^1 ... pk^ck)
p比较好求直接分解质因数就行问题是(pk^0 pk^1 ... pk^ck)要怎么求
假设 t 1存在操作 t p * t 1
则有t p * 1 1 p 1
t p * (p 1) 1 p^2 p 1
t p * (p^2 p 1) 1 p^3 p^2 p^1 1
……
typedef long long LL;
int mod 1e9 7;int main()
{unordered_mapint, int primes;int n;cin n;while (n--){int a;cin a;//对每个数进行质因数分解for (int i 2; i a / i; i){if (a % i 0){primes[i];a / i;}}if (a 1)primes[a];}LL result 1;for (auto prime : primes){LL t 1;int a prime.first, b prime.second;while (b--){t (t * a 1) % mod;}result result * t % mod;}cout result endl;return 0;
}
常见模运算
(a * b) mod c ((a mod c) * (b mod c)) mod c
(a b) mod c ((a mod c) (b mod c)) mod c
(a - b) mod c ((a mod c) - (b mod c)) mod c
(a ^ b) mod c ((a mod c) ^ b) mod c
(a / b) mod c ! ((a mod c) / (b mod c)) mod c除法的模运算不满足这样的等式3.欧几里得算法辗转相除法-- 求最大公约数
gcd(a, b) gcd(b, a mod b);
gcd代表最大公约数
int gcd(int a, int b)
{//if (a b) swap(a, b);//这一步不需要因为会自己调整比如gcd(6,16),下一次递归就变成了gcd(16,6)return b ? gcd(b, a % b) : a;
}
