베르트랑 공준 성공 출처 다국어
한국어
시간제한 메모리 비율
| 1 초 | 256 MB | 44439 | 18273 | 14914 | 41.846% |
문제
베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.
이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.
예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)
자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.
입력의 마지막에는 0이 주어진다.
출력
각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.
제한
- 1 ≤ n ≤ 123,456
예제 입력 1
1
10
13
100
1000
10000
100000
0
예제 출력 1
1
4
3
21
135
1033
8392
JAVA [자바] - 소수 구하는 알고리즘 및 구현
들어가기 전에 소수 [Prime Number] 소수의 정의는 1보다 큰 자연수 중 1 과 그 수 자기 자신만을 약수로 갖는 자연수를 의미한다는 점은 누구나 알고 있을 것이다. 즉, 소수의 약수는 2개만을 갖고,
st-lab.tistory.com
get_prime() 메서드는 위 링크에 자세히 설명되어 있습니다!
지문에서 n > 123456 이므로 2n 은 최대 246912이고 0부터 시작하므로 246912 + 1 = 246913
boolean 배열을 246913의 길이만큼 만들어 준다
BufferedReader로 입력값을 받고,
소수 얻는 메서드를 후에
while문으로 반복문을 시작한다
예시에 0이 들어오는 값이 있어서
만약 들어온 값 n이 0일 때는 break를 걸어서 while문을 탈출시킨다
count라는 int형 변수를 만들어서 소수 개수를 세는데,
이때 For문으로 들어온 값 n + 1부터 2를 곱한 값 2n까지 반복문을 돌린다
그때 If조건문으로 소수인 인덱스를 만나면 카운트를 늘려준다
그리고 StringBuilder에 카운트를 담고
한 줄씩 끊기 위해서 '\n'도 append 해준다
마지막으로 sb를 출력해주면 된다
'TIL > Algorithm' 카테고리의 다른 글
| Java 백준 1085번 문제 - 직사각형 탈출 (0) | 2021.10.25 |
|---|---|
| Java 백준 9020번 문제 - 골드바흐의 추측 (0) | 2021.10.24 |
| Java 백준 1929번 문제 - 에라토스테네스의 체 (0) | 2021.10.22 |
| Java 백준 11653번 문제 - 소인수분해 (0) | 2021.10.21 |
| Java 백준 2581번 문제 - 소수 (0) | 2021.10.20 |
