文章目录
前言
一、质数，质因数
二、例题，代码
AcWing 866. 试除法判定质数
AC代码
AcWing 867. 分解质因数
本题解析：
AC代码
AcWing 868. 筛质数
诶氏筛法
线性筛法
三、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解数学知识：质数，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、质数，质因数
质数即素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数。约数（又称因数）是指若整数a除以整数b(b≠0)除得的商正好是整数而没有余数，就说a能被b整除，或b能整除a，其中a称为b的倍数，b称为a的约数。每个合数都可以写成几个质数相乘的形式,这几个质数就都叫做这个合数的质因数
二、例题，代码
AcWing 866. 试除法判定质数
本题链接：AcWing 866. 试除法判定质数
本博客提供本题截图：
AC代码
#include <cstdio> using namespace std; bool f(int n) { if (n < 2) return false; for (int i = 2; i <= n / i; i ++ ) if (n % i == 0) return false; return true; } int main() { int m, n; scanf("%d", &m); while (m -- ) { int n; scanf("%d", &n); if (f(n)) puts("Yes"); else puts("No"); } return 0; }
AcWing 867. 分解质因数
本题链接：AcWing 867. 分解质因数
本博客提供本题截图：
本题解析：
分解质因数的结果为把一个数化成下图形式：
AC代码
#include <iostream> #include <algorithm> using namespace std; void divide(int 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; } int main() { int n; cin >> n; while (n -- ) { int x; cin >> x; divide(x); } return 0; }
