前缀知识
算术基本定理
算术基本定理，又称为**正整数的唯一分解定理**，即：每个大于1的自然数，要么本身就是质数，要么可以写为2个或以上的质数的积，而且这些质因子按大小排列之后，写法仅有一种方式。
例如：
$$
936=2^{3} \times 3 \times 17^{2}, 1200=2^{4} \times 3 \times 5^{2}, 5207=41 \times 127
$$
质因子相关模板：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
long n = sc.nextLong();
int ans = 0;
// 任何一个数的质因子大于根号n的要么没有要么只有一个
for (int i = 2; i <= n / i; i++) {
if (n % i == 0) {
ans++;
// 设置系数
int cnt = 0;
while (n % i == 0) {
n /= i;
cnt++;
}
System.out.println("质数为" + i + "的幂次系数是" + cnt);
}
}
// // 任何一个数的质因子大于根号n的要么没有要么只有一个
if (n > 1) {
System.out.println(n + "幂次系数是" + 1);
ans++;
}
System.out.println("质因子种类个数为" + ans);
}
}
}
|
例题一：
问题描述
给定正整数 n, 请问有多少个质数是 n 的约数。
输入格式
输入的第一行包含一个整数 n 。
输出格式
输出一个整数, 表示 n 的质数约数个数。
样例输入
样例输出
样例说明
396 有 2,3,11 三个质数约数。
评测用例规模与约定
对于 30% 的评测用例, 1≤n≤10000 。
对于 60% 的评测用例, 1≤n≤10^9 。
对于所有评测用例, 1≤n≤10^16。
运行限制
程序代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| package bisai;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
long n = sc.nextLong();
int ans = 0;
// 任何一个数的质因子大于根号n的要么没有要么只有一个
for (int i = 2; i <= n / i; i++) {
if (n % i == 0) {
ans++;
// 设置系数
int cnt = 0;
while (n % i == 0) {
n /= i;
cnt++;
}
}
}
// // 任何一个数的质因子大于根号n的要么没有要么只有一个
if (n > 1) {
ans++;
}
System.out.println(ans);
}
}
}
|
例题二:
问题描述
任何一个大于 1 的正整数都能被分解为若干个质数相乘, 比如 28=2×2×728=2×2×7 被分解为了三个质数相乘。请问在区间 [2333333, 23333333] 中有多少个正整数 可以被分解为 12 个质数相乘?
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。
运行限制
程序代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
long n = sc.nextLong();
int ans = 0;
for (int j = 2333333; j < 23333333; j++) {
int temp = j;
int num = 0;
for (int i = 2; i <= temp / i; i++) {
while (temp % i == 0) {
temp /= i;
num++;
}
}
if (temp > 1)
num++;
if (num == 12)
ans++;
}
System.out.println(ans);
}
}
}
|
