반응형
문제가 개떡같이 길게 쓰여 있지만 간단하게 풀면
n을 입력하면 n보다 크고 2n보다 작은 소수의 개수를 출력하는 문제이다.
0을 입력할 때 까지 계속 반복하면 끝~
저번 소수문제와 같이 이렇게 범위가 주어지고 소수를 구하는 문제는 에라토스테네스의 체 방법을 이용하면 된다.
마찬가지로 같은 방법을 이용해서 풀어보도록 하자.
에라토스테네 체의 관한 자세한 풀이는 요기에 있다.
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
|
import java.util.Scanner;
public class Main {
//baekjoon 4948 베르트랑 공준 기본수학2
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(true) {
int n = sc.nextInt();
if(n==0) {
break;
}
boolean arr[] = new boolean[2*n+1];
arr[0] = true;
arr[1] = true;
for(int i=2; i<=Math.sqrt(2*n+1); i++) {
for(int j=i*i; j<2*n+1; j+=i) {
arr[j] = true;
}
}
int cnt = 0;
for(int i=n+1; i<2*n+1; i++) {
if(arr[i] == false) {
cnt++;
}
}
System.out.println(cnt);
}
}
}
|
cs |
9행 : 0을 입력할 때 까지 반복해야 하므로 while(true)로 무한루프를 돌린다.
14행 : 소수 찾을 범위가 n보다 크고 2n보다 작으므로 2*n+1 크기로 bool 값 배열을 선언한다. (기본 false로 초기화됨)
15, 16행 : 2부터 검사할 것이므로 0과 1은 소수가 아닌 의미로 미리 true값을 준다.
18행 : 2 부터 (2*n+1)의 제곱근 까지 검사하고
19행 : j는 i의 제곱부터 범위까지 검사한다. 제곱한 수는 소수가 될 수 없다. j 에 i값씩 더해가며 반복
(처음에 2이므로 4, 6, 8 ...은 소수가 아님을 체크한다. 다음 수는 3이 들어와 9, 12, 15... 반복)
24행 : n보다 크고 2n보다 작거나 같으므로 i=n+1; i<2*n+1 로 false값을 체크한다.
29행 cnt 출력~
반응형
'프로그래밍 > 백준 알고리즘 코드' 카테고리의 다른 글
백준 1085 자바 직사각형에서 탈출 [기본수학2] (0) | 2021.05.06 |
---|---|
백준 9020번 자바 골드바흐의 추측 [기본수학2] (0) | 2021.05.05 |
백준 1929번 자바 JAVA 소수 구하기 [기본수학2] (0) | 2021.04.29 |
백준 11653번 JAVA 소인수분해 [기본 수학2] (0) | 2021.04.27 |
백준 2581번 자바 소수 [기본 수학2] 에라토스테네스의 체 (0) | 2021.04.26 |
댓글