目录
一、判定质数
1. 代码
#include <iostream>
using namespace std;
bool is_prime(int x)
{
// 1不是质数, 需要特判
if (x == 1) return 0;
// i从2枚举到根号x
for (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枚举到根号x
for (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和它的个数1
if (x > 1) cout << x << " " << 1 << endl;
}
int main()
{
int n;
cin >> n;
while (n -- )
{
int x;
cin >> x;
// 拆解x
decompose(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 long
for (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;
}