中国站长素材网,盐城网站建设hx1818,安平谁做网站好,确定网站开发团队目录 一、判定质数思路分析代码实现 二、分解质因数思路分析典型题目代码实现 三、质数筛经典题目思路分析1. 朴素筛法2. 埃氏筛法3. 欧拉筛法 一、判定质数
思路分析
由于每个合数的因子是成对出现的#xff0c;即如果 d d d 是 n n n 的因子#xff0c;那么 n d \frac… 目录 一、判定质数思路分析代码实现 二、分解质因数思路分析典型题目代码实现 三、质数筛经典题目思路分析1. 朴素筛法2. 埃氏筛法3. 欧拉筛法 一、判定质数
思路分析
由于每个合数的因子是成对出现的即如果 d d d 是 n n n 的因子那么 n d \frac{n}{d} dn 也是 n n n 的因子故从 1 1 1 到 n n n 的枚举可以缩减到 1 1 1 到 n \sqrt{n} n 即让 d ≤ n d d \leq \frac{n}{d} d≤dn从而得到 d ≤ n d \leq \sqrt{n} d≤n 。
代码实现
bool is_prime(int n)
{if (n 2) return false;for (int i 2; i n / i; i){if (n % i 0) return false;}return true;
}时间复杂度 O ( n ) O(\sqrt{n}) O(n ) 二、分解质因数
思路分析
每个合数都是由质数相乘得到的。合数可以写成质因数的乘积这是数论中的一个基本命题。 例如: 12 2 * 2 * 3 18 2 * 3 * 3 24 2 * 2 * 2 * 3 ① 对于任何一个合数 n n n在它的质因数分解中至多有一个质因子大于 n \sqrt{n} n 。
② 同时也可以推出对任何一个合数 n n n在它的质因数分解中至少会有一个质因子小于或等于 n \sqrt{n} n 。 典型题目
题目描述 给定 n n n 个正整数 a i a_i ai将每个数分解质因数并按照质因数从小到大的顺序输出每个质因数的底数和指数。
输入格式 第一行包含整数 n n n。
接下来 n n n 行每行包含一个正整数 a i a_i ai。
输出格式 对于每个正整数 a i a_i ai按照从小到大的顺序输出其分解质因数后每个质因数的底数和指数每个底数和指数占一行。
每个正整数的质因数全部输出完毕后输出一个空行。
数据范围 1 ≤ n ≤ 100 , 2 ≤ a i ≤ 2 ∗ 1 0 9 1≤n≤100,2≤a_i≤2*10^9 1≤n≤100,2≤ai≤2∗109
输入样例
2
6
8输出样例
2 1
3 12 3代码实现
#define _CRT_NO_SECURE_WARNINGS
#includeiostreamusing namespace std;void divide(int x)
{for (int i 2; i x / i; i) // 遍历出所有小于或等于sqrt(n)的质因子{if (x % i 0){int cnt 0;while (x % i 0){cnt;x / i;}cout i cnt endl;}}// 输出大于sqrt(n)的质因子或是质数本身if (x 1) cout x 1 endl;cout endl;
}
int main()
{int n;cin n;while (n--){int x;cin x;divide(x);}return 0;
}时间复杂度在 O ( log n ) O(\log n) O(logn) 与 O ( n ) O(\sqrt n) O(n )之间 解释若 n n n 为 2 2 2 的倍数时间复杂度将会变为 O ( log n ) O(\log n) O(logn)。 三、质数筛
经典题目
题目描述 给定一个正整数 n n n请你求出 1 ∼ n 1∼n 1∼n 中质数的个数。
输入格式 共一行包含整数 n n n。
输出格式 共一行包含一个整数表示 1 ∼ n 1∼n 1∼n 中质数的个数。
数据范围 1 ≤ n ≤ 1 0 6 1≤n≤10^6 1≤n≤106
输入样例
8输出样例
4思路分析 通过将素数的倍数筛掉的方法剩余存留的则全为质数。
筛完后 P P P 与 2 2 2 ~ ( P − 1 P-1 P−1) 之间不存在倍数关系即 P P P 无质因子在 2 2 2 ~ ( P − 1 P-1 P−1) 之间。 1. 朴素筛法 通过将2~n的所有数的倍数筛掉的方法来得到范围内所有的质数 #define _CRT_NO_SECURE_WARNINGS
#includeiostreamusing namespace std;const int N 1e6 10;
int prime[N], cnt;
bool st[N];void get_prime(int n)
{for (int i 2; i n; i){if (!st[i]){prime[cnt] i;}for (int j 2 * i; j n; j i) st[j] true; // 将2~n所有数的倍数都打上标记}
}
int main()
{int n;cin n;get_prime(n);cout cnt endl;return 0;
}时间复杂度 O ( n log n ) O(n \log n) O(nlogn) n 2 n 3 n 4 . . . n n n ( 1 2 1 3 1 4 . . . 1 n ) \frac{n}{2} \frac{n}{3} \frac{n}{4} ... \frac{n}{n} n(\frac{1}{2} \frac{1}{3} \frac{1}{4} ... \frac{1}{n}) 2n3n4n...nnn(213141...n1)
调和级数 lim n → ∞ ( 1 2 1 3 1 4 . . . 1 n ) ln n c \lim_{n \to \infty} (\frac{1}{2} \frac{1}{3} \frac{1}{4} ... \frac{1}{n}) \ln n c limn→∞(213141...n1)lnnc (欧拉常数 c 0.577 c 0.577 c0.577)
因此可得时间复杂度为 O ( n log n ) O(n \log n) O(nlogn) 2. 埃氏筛法 优化了朴素筛法只将2~n的质数的倍数筛掉的方法来得到范围内所有的质数 #define _CRT_NO_SECURE_WARNINGS
#includeiostreamusing namespace std;const int N 1e6 10;
int prime[N], cnt;
bool st[N];void get_prime(int n)
{for (int i 2; i n; i){if (st[i]) continue;prime[cnt] i;for (int j 2 * i; j n; j i) st[j] true; // 将2~n所有质数的倍数都打上标记}
}
int main()
{int n;cin n;get_prime(n);cout cnt endl;return 0;
}时间复杂度为 O ( n log log n ) O(n \log \log n) O(nloglogn)
质数定理在 1 1 1 到 n n n 之间的质数个数约等于 n ln n \frac{n}{\ln n} lnnn 3. 欧拉筛法
核心思想在埃氏筛法的基础上让每个合数只被它的最小质因子筛选一次以达到不重复的目的。
步骤
从 i 2 i 2 i2 开始如果 i i i 还没有被筛掉则将 i i i 加入至素数列表中。遍历当前素数列表 p r i m e [ ] prime[] prime[]筛去 i ∗ p r i m e [ j ] i ∗ prime[j] i∗prime[j]。 保证 p r i m e [ j ] ∗ i prime[j] ∗ i prime[j]∗i 不能越界因为越界了对结果没意义。即 i ∗ p r i m e [ j ] ≤ n i ∗ prime[j] \leq n i∗prime[j]≤n当遍历到能整除 i 的素数 p r i m e [ j ] prime[j] prime[j] 时筛去 i ∗ p r i m e [ j ] i ∗ prime[j] i∗prime[j]停止对素数列表的遍历。重复 2 , 3 , 4 2,3,4 2,3,4直到所有不超过 n n n 的整数都被遍历过素数列表中的元素即为所求的不超过 n n n 的所有素数。
#define _CRT_NO_SECURE_WARNINGS
#includeiostreamusing namespace std;const int N 1e6 10;
int cnt, prime[N];
bool st[N];void get_prime(int n)
{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; // 只被它的最小质因子筛选一次}}
}
int main()
{int n;cin n;get_prime(n);cout cnt endl;return 0;
}若 n 1 0 6 n10^6 n106欧拉筛和埃氏筛所花费的时间差不多但是若 n 1 0 7 n10^7 n107欧拉筛会比埃氏筛快了大概一倍。 文章转载自： http://www.morning.gtqws.cn.gov.cn.gtqws.cn http://www.morning.wsyst.cn.gov.cn.wsyst.cn http://www.morning.hkpn.cn.gov.cn.hkpn.cn http://www.morning.tbqbd.cn.gov.cn.tbqbd.cn http://www.morning.pphbn.cn.gov.cn.pphbn.cn http://www.morning.jkftn.cn.gov.cn.jkftn.cn http://www.morning.jprrh.cn.gov.cn.jprrh.cn http://www.morning.zcsch.cn.gov.cn.zcsch.cn http://www.morning.fypgl.cn.gov.cn.fypgl.cn http://www.morning.hyyxsc.cn.gov.cn.hyyxsc.cn http://www.morning.rxkq.cn.gov.cn.rxkq.cn http://www.morning.hnkkm.cn.gov.cn.hnkkm.cn http://www.morning.tralution.cn.gov.cn.tralution.cn http://www.morning.mdxwz.cn.gov.cn.mdxwz.cn http://www.morning.zmlnp.cn.gov.cn.zmlnp.cn http://www.morning.pgrsf.cn.gov.cn.pgrsf.cn http://www.morning.nkkpp.cn.gov.cn.nkkpp.cn http://www.morning.wjrtg.cn.gov.cn.wjrtg.cn http://www.morning.zcsyz.cn.gov.cn.zcsyz.cn http://www.morning.fbxlj.cn.gov.cn.fbxlj.cn http://www.morning.newfeiya.com.cn.gov.cn.newfeiya.com.cn http://www.morning.jkzq.cn.gov.cn.jkzq.cn http://www.morning.mrfjr.cn.gov.cn.mrfjr.cn http://www.morning.skrrq.cn.gov.cn.skrrq.cn http://www.morning.geledi.com.gov.cn.geledi.com http://www.morning.xdlwm.cn.gov.cn.xdlwm.cn http://www.morning.jnzfs.cn.gov.cn.jnzfs.cn http://www.morning.skql.cn.gov.cn.skql.cn http://www.morning.thjqk.cn.gov.cn.thjqk.cn http://www.morning.dpsyr.cn.gov.cn.dpsyr.cn http://www.morning.mpxbl.cn.gov.cn.mpxbl.cn http://www.morning.xtdms.com.gov.cn.xtdms.com http://www.morning.gwsll.cn.gov.cn.gwsll.cn http://www.morning.jgcxh.cn.gov.cn.jgcxh.cn http://www.morning.wbqt.cn.gov.cn.wbqt.cn http://www.morning.nmrtb.cn.gov.cn.nmrtb.cn http://www.morning.skkmz.cn.gov.cn.skkmz.cn http://www.morning.hwnnh.cn.gov.cn.hwnnh.cn http://www.morning.nqpxs.cn.gov.cn.nqpxs.cn http://www.morning.hnrqn.cn.gov.cn.hnrqn.cn http://www.morning.lcbt.cn.gov.cn.lcbt.cn http://www.morning.yuanshenglan.com.gov.cn.yuanshenglan.com http://www.morning.dycbp.cn.gov.cn.dycbp.cn http://www.morning.drndl.cn.gov.cn.drndl.cn http://www.morning.ktfnj.cn.gov.cn.ktfnj.cn http://www.morning.mcjyair.com.gov.cn.mcjyair.com http://www.morning.pqsys.cn.gov.cn.pqsys.cn http://www.morning.hsjrk.cn.gov.cn.hsjrk.cn http://www.morning.wmdbn.cn.gov.cn.wmdbn.cn http://www.morning.bxhch.cn.gov.cn.bxhch.cn http://www.morning.ntqqm.cn.gov.cn.ntqqm.cn http://www.morning.pmdlk.cn.gov.cn.pmdlk.cn http://www.morning.pxbky.cn.gov.cn.pxbky.cn http://www.morning.qnhpq.cn.gov.cn.qnhpq.cn http://www.morning.tjwlp.cn.gov.cn.tjwlp.cn http://www.morning.rfmzc.cn.gov.cn.rfmzc.cn http://www.morning.prjns.cn.gov.cn.prjns.cn http://www.morning.wmcng.cn.gov.cn.wmcng.cn http://www.morning.jprrh.cn.gov.cn.jprrh.cn http://www.morning.ghxkm.cn.gov.cn.ghxkm.cn http://www.morning.zlrsy.cn.gov.cn.zlrsy.cn http://www.morning.fwzjs.cn.gov.cn.fwzjs.cn http://www.morning.cnlmp.cn.gov.cn.cnlmp.cn http://www.morning.djxnn.cn.gov.cn.djxnn.cn http://www.morning.rxfbf.cn.gov.cn.rxfbf.cn http://www.morning.qstjr.cn.gov.cn.qstjr.cn http://www.morning.mhwtq.cn.gov.cn.mhwtq.cn http://www.morning.pjwrl.cn.gov.cn.pjwrl.cn http://www.morning.kgnnc.cn.gov.cn.kgnnc.cn http://www.morning.pjrgb.cn.gov.cn.pjrgb.cn http://www.morning.dkbgg.cn.gov.cn.dkbgg.cn http://www.morning.gsqw.cn.gov.cn.gsqw.cn http://www.morning.mtymb.cn.gov.cn.mtymb.cn http://www.morning.sjwqr.cn.gov.cn.sjwqr.cn http://www.morning.yggdq.cn.gov.cn.yggdq.cn http://www.morning.mlwhd.cn.gov.cn.mlwhd.cn http://www.morning.dycbp.cn.gov.cn.dycbp.cn http://www.morning.shinezoneserver.com.gov.cn.shinezoneserver.com http://www.morning.xhftj.cn.gov.cn.xhftj.cn http://www.morning.rnnq.cn.gov.cn.rnnq.cn
