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
- 9장
- java의 정석
- 1300번
- 2206번
- 백준
- java
- 11286번
- Spring
- 17장
- BOJ
- Design Pattern
- 11758번
- 클린코드
- springboot
- 2156번
- 가장 긴 증가하는 부분 수열2
- 1043번
- 2166번
- Dxerr.h
- 코딩테스트
- 코딩 테스트
- 냄새와 휴리스틱
- Design Patterns
- SerialDate 리펙터링
- Adapater Pattern
- 10830번
- 프로그래머스
- 자바의 정석
- DxTrace
- programmers
Archives
- Today
- Total
Don't give up!
[백준] 1929번 : 소수 구하기 (java) 본문
어떻게 생각하고 문제를 풀었는가?
소수가 아닌 수는 소수로 나누어 떨어져야 합니다.
따라서 2부터 시작하여 소수를 찾고, 해당 값의 곱으로 나타내어지는 수들을 소수가 아닌 수라고 결정할 수 있으므로 이를 구현한다면 문제를 해결할 수 있을 것이라고 생각하였습니다.
코드
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int M = Integer.parseInt(tokenizer.nextToken());
int N = Integer.parseInt(tokenizer.nextToken());
reader.close();
boolean[] primes = new boolean[N+1];
Arrays.fill(primes,true);
primes[1] = false;
for(int i=2; i*i<=N; i++){
if(primes[i]){
for(int j= i*i; j<=N; j+=i){
primes[j] = false;
}
}
}
for(int i=M; i<=N; i++){
if(primes[i]){
System.out.println(i);
}
}
}
}
N개의 숫자가 소수인지 아닌지 확인할 수 있도록 boolean 배열로 정의하였습니다.
모든 숫자를 소수라고 가정하고, 2부터 시작하여 해당 소수의 배수에 해당하는 index의 boolean 값을 false로 바꿈으로써 N개의 숫자들 중 소수인 숫자들을 확인할 수 있습니다.
'Coding Test > BOJ' 카테고리의 다른 글
[백준] 2206번 : 벽 부수고 이동하기 (java) (0) | 2021.08.10 |
---|---|
[백준] 1022번 : 소용돌이 예쁘게 출력하기 (java) (0) | 2021.08.07 |
[백준] 1068번 : 트리 (java) (0) | 2021.07.23 |