-
2960) 에라토스테네스의 체 - Java백준코딩일기 2020. 1. 29. 17:58
문제 )
https://www.acmicpc.net/problem/2960
에라토스테네스의 체 정의
저는 이 문제를 직면하기전까지도 에라토스테네스의 체가 무엇인지도 몰랐습니다,,,
그래서 혹시나 저와같은 분들이 계실까봐 위키백과에서 너무 잘 설명해주고,
시뮬레이션도 넣어놔서 한 번 보시라고 링크 걸어둡니다!코드 )
12345678910111213141516171819202122232425262728293031323334353637383940import java.util.StringTokenizer;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));StringTokenizer st = new StringTokenizer(br.readLine(), " ");int N = Integer.valueOf(st.nextToken());int K = Integer.valueOf(st.nextToken());// default값이 false이므로 0과 1번째에 따로 false 값을 넣지않아도 됨boolean[] primeNum = new boolean[N+1];// 2부터 N까지 모든 정수에 true값을 넣음for(int i=2; i<=N; i++)primeNum[i] = true;int count = 0; // 나중에 K번째 지워지는 수를 찾는 변수for(int i=2; i<=N; i++) { // 2부터 N까지의 수를 돌면서 검사for(int j=i; j<=N; j+=i) { // 2부터 가장작은 수부터 배수로 검사하므로// 마지막 조건이 j=j+i를 한 값// 이미 검사가 되어 false 값이 들어갔다면 넘어감if( !primeNum[j]) continue;// 아직 검사가 안된값이라면 false 값을 넣고 count를 증가시킴primeNum[j] = false;count++;if( count == K) { //count 가 K 즉, 찾는 순서와 같다면 j를 출력}}}}} cs'백준코딩일기' 카테고리의 다른 글
6588) 골드바흐의 추측 (0) 2020.01.29 1929) 소수 구하기 - Java (0) 2020.01.29 11727) 2×n 타일링 2 - Java (0) 2020.01.24 11726) 2×n 타일링 - Java (0) 2020.01.24 2004) 조합 0의 개수 - Java (0) 2020.01.15