반응형
🔺 문제
🔺 코드
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
|
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
long Min = Long.parseLong(st.nextToken());
long Max = Long.parseLong(st.nextToken());
long[] A = new long[10000001];
// 배열 초기화
for(int i = 2 ; i < A.length ; i++) {
A[i] = i;
}
for(int i = 2 ; i <= Math.sqrt(A.length) ; i++) { // 제곱근까지만 수행
if(A[i] == 0) continue; // 소수가 아니면 넘어감
for(int j = i + i ; j < A.length ; j += i) { // 배수 지우기
A[j] = 0;
}
}
int cnt = 0;
for(int i = 2 ; i < A.length ; i++) {
if(A[i] != 0) {
long tmp = A[i]; // 현재 소수
// 🔔 소수를 N제곱한 값이 B보다 커질 때까지 반복문 실행
while((double)A[i] <= (double)Max / (double)tmp) {
if((double)A[i] >= (double)Min / (double)tmp) { // 🔔 소수를 N제곱한 값이 M보다 크거나 같으면 => 거의 소수
cnt++;
}
tmp *= A[i];
}
}
}
System.out.println(cnt);
}
}
|
cs |
✅ 해결 아이디어
✔ 에라토스테네스의 체
💥 유의사항
⇨ (반복문 범위) 10의 14제곱의 제곱근인 10의 7제곱까지 반복
⇨ N제곱한 값을 구하다가 범위가 long형을 초과하는 경우가 발생하므로 이항 정리로 처리
- (N의 k 제곱) vs B가 아닌, N vs B / (N의 k-1 제곱)으로 비교 (37,38번째 줄)
🔺 다른 풀이들
https://www.acmicpc.net/source/29360286
💬 느낀 점
37,38번째 줄 처럼 조건을 잘 생각하고 적용시켜야겠다..
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V | 6/20 |
반응형
'코테 > 백준' 카테고리의 다른 글
[백준/JAVA] 1016번: 제곱 ㄴㄴ 수 (0) | 2023.04.25 |
---|---|
[백준/JAVA] 1747번: 소수&팰린드롬 (0) | 2023.04.25 |
[백준/JAVA] 1929번: 소수 구하기 (0) | 2023.04.25 |
[백준/JAVA] 1541번: 잃어버린 괄호 (0) | 2023.04.24 |
[백준/JAVA] 1931번: 회의실 배정 (0) | 2023.04.24 |