https://www.acmicpc.net/problem/1456
1456번: 거의 소수
어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.
www.acmicpc.net
정수론 문제는 처음이네요?
이 문제에서 요구하는 거의 소수란, 어떤 소수의 N제곱(N >= 2) 꼴이 되는 수라고 합니다.
즉, 8은 2의 3제곱이므로 거의 소수이며, 1024는 2의 10제곱이므로 거의 소수가 됩니다.
주어지는 [A ~ B]의 구간에서 거의 소수의 갯수를 구하는 문제입니다.
먼저 소수를 알아야하므로 에라토스테네스의 체로 소수를 모두 구합니다.
범위가 10^14까지인데, 어떤 소수의 제곱이 10^14이하가 되는거라 10^7까지의 소수만 구하도록 합니다.
그리고 2부터 1씩 증가하면서 i가 소수인지 확인을 합니다.
소수가 맞다면 i의 n제곱이 r이하일 동안에는 계속 i를 곱해줍니다.
이 과정에서 l 이상, r 이하일 동안은 카운팅을 진행합니다.
어차피 소수 i의 n제곱이고, 그 수는 다른 소수를 곱해서는 도달할 수 없는 수입니다.
이 과정에서 문제가 있었습니다.
i를 계속 곱하는 과정에서 수가 long 범위를 벗어나는 경우입니다.
어떤 소수를 n제곱 하면 long 범위를 초과했고, 음수 값이 되어 r을 넘는 값임에도 계속 반복문을 도는 문제가 있었습니다.
결국에는 WA를 받게되었고, i를 1번 덜 곱하는 방법으로 해결하였습니다.
i * i <= r 이라는 식을 i <= r / i 로 변경하여 곱셈을 진행하였고, 이 방법으로는 long 범위를 초과하지 않는다는 것을 확인했습니다.
|
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
41
42
43
44
45
46
47
48
49
50
51
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private final static int MAX = 10000001;
private static boolean prime[] = new boolean[MAX];
private static long l, r;
private static void init() {
for (int i = 2; i * i < MAX; i++) {
if (prime[i]) continue;
for (int j = 2; i * j < MAX; j++) {
prime[i * j] = true;
}
}
}
private static void func() {
init();
int ret = 0;
for (long i = 2; i * i <= r; i++) {
if (prime[(int) i]) continue;
long mul = i;
while (mul <= r / i) {
mul *= i;
if (mul >= l) {
ret++;
}
}
}
System.out.println(ret);
}
private static void input() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
l = Long.parseLong(st.nextToken());
r = Long.parseLong(st.nextToken());
}
public static void main(String[] args) throws Exception {
input();
func();
}
}
|
cs |