目录
一、判定质数
1. 代码
二、分解质因数
1. 质因数的概念
2. 代码
三、筛质数——获取1~n中所有质数的个数
1. 合数的概念
2. 代码
一、判定质数
1. 代码
#include <iostream>
using namespace std;bool is_prime(int x)
{// 1不是质数, 需要特判if (x == 1) return 0;// i从2枚举到根号xfor (int i = 2; i <= x / i; i ++ )if (x % i == 0) return 0;return 1;
}int main()
{int n;cin >> n;while (n -- ){int a;cin >> a;cout << (is_prime(a) ? "Yes" : "No") << endl;}return 0;
}
二、分解质因数
1. 质因数的概念
这道题的目的是找到x这个数的质因数的底数和指数。例如280这个数,可以看成2^3 * 5^1 * 7^1,其中2、5和7分别是三个质因数的底数,3、1、1分别是三个质因数的指数。
2. 代码
#include <iostream>
using namespace std;// 假设拆280
void decompose(int x)
{// i从2枚举到根号xfor (int i = 2; i <= x / i; i ++ ){if (x % i == 0){// s代表质数i的个数int s = 0;while (x % i == 0) s ++, x /= i;cout << i << " " << s << endl;}}// 质数x和它的个数1if (x > 1) cout << x << " " << 1 << endl;
}int main()
{int n;cin >> n;while (n -- ){int x;cin >> x;// 拆解xdecompose(x);cout << endl;}return 0;
}
三、筛质数——获取1~n中所有质数的个数
1. 合数的概念
质数和合数是一对相反的概念; 质数是除数只有1和它本身, 合数是除了1和它本身还有别的除数。
2. 代码
#include <iostream>
using namespace std;const int N = 1e6 + 10;// vis[i]代表i这个数是否是合数; vis[4]=1代表4这个数是合数, vis[3]=0代表3这个数不是合数, 是质数
// prime数组记录所有的质数, prime[i]代表第i个质数的值; prime[1]=2代表1~n第一个质数是2
// cnt记录prime数组中质数的个数, 也就是1~n中所有质数的个数
int vis[N], primes[N], cnt;// 获取1~n所有的质数, 存储在prime数组中
void get_primes(int n)
{// 从2开始枚举所有数for (int i = 2; i <= n; i ++ ){// 如果i是质数, 记录下来if (!vis[i]) primes[ ++ cnt] = i;// 不管i是质数还是合数, i*prime[j]一定是合数; i*prime[j]有可能爆int, 把它的结果提升成long longfor (int j = 1; 1LL * i * primes[j] <= n; j ++ ){// 记录i*prime[j]是合数vis[i * primes[j]] = 1;// 如果i是质数, prime[j]就是它本身; 如果i是合数, prime[j]是它的除数中的最小质数if (i % primes[j] == 0) break;}}
}int main()
{int n;cin >> n;// 获取1~n中所有的质数get_primes(n);// 输出1~n中所有质数的个数cout << cnt << endl;return 0;
}