250x250
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 알고리즘
- 백준15652
- 볼륨 만들기
- N과M
- 완탐
- 자바
- Bfs와DFS
- 파티션 크기 조정
- 코테준비
- 재귀함수
- 전화번호속의암호
- 주사위굴리기2
- java
- 중복순열
- 삼성역테
- 23288
- 백준
- 정올 1620
- 백준13458
- 중복조합
- D드라이브생성
- 에라토스테네스의채
- 완전탐색
- 알고리즘개념
- 자바 코테
- 코테
- 백준2251
- 정보처리기사
- BFS
- 순열
Archives
- Today
- Total
뚱땅뚱땅
[문제] 백준 4948번 베트르랑 공준 - 소수 본문
728x90
* 출처: 백준 단계별로 풀어보기 기본수학2
에스트라테네스의 체를 이용해 문제를 풀었다.
여기서 주의할 점은 반복문 돌릴 때 인덱스 범위이다.
i*i를 할 때 MAX_NUM을 넘어가면 안되고, 2*n할 떄도 마찬가지로 MAX_NUM을 넘어가면 안된다!
이부분만 주의하면 나머지는 앞선 소수 찾기 문제와 동일하다.
import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static boolean[] prime;
public static int MAX_NUM = 123456 * 2;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int n = 0;
prime = new boolean[MAX_NUM + 1];
initPrime();
while ((n = Integer.parseInt(in.readLine())) != 0) {
int ans = 0;
for(int i=n+1;i<=2*n;i++) {
if(i>MAX_NUM) break;
if(!prime[i]) ans++;
}
sb.append(ans).append('\n');
}
System.out.println(sb);
}
static void initPrime() {
prime[0] = prime[1] = true;
for (int i = 2; i <= MAX_NUM; i++) {
if (prime[i])
continue;
if(i*i>MAX_NUM) break;
for (int j = i * i; j <= MAX_NUM; j += i) {
prime[j] = true;
}
}
}
}
728x90
'알고리즘 > 백준' 카테고리의 다른 글
[문제] 백준 17478번 재귀함수가 뭔가요? (0) | 2021.02.01 |
---|---|
[문제]백준 9020번 골드바흐의 추측 (0) | 2021.01.30 |
[문제] 백준 1929번 소수 구하기 - 에라토스테네스의 체 이용하기 (0) | 2021.01.30 |
[문제] 백준 11653번 소인수분해 (0) | 2021.01.30 |
[문제] 백준 2581번 소수 (0) | 2021.01.30 |
Comments