백준 2960번 : 에라토스테네스의 체 [Java]

https://www.acmicpc.net/problem/2960

2960번: 에라토스테네스의 체

 

전체코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		int N, K;
		Scanner sc = new Scanner(System.in); //스캐너 객체 생성
		
		N = sc.nextInt(); //정수 입력받기
		K = sc.nextInt(); //몇번째 숫자
		int[] num = new int[N+1]; //입력받은 수 배열 만들기
		for(int j = 0;j<N+1;j++) {
			if(j == 0 || j == 1) {
				num[j] = 0;
			}else {
				num[j] = j;
			}
		}
		
		int p = 0;
		int k_count = 0; //k_count = K이면 종료
		int out = 0;
	
		for(int k = 2; k < num.length; k++) {
			if(num[k] != 0) {
				for(p = k; p<num.length; p+=k) { //배수들 다 0으로 만들기
					
					out = num[p]; //삭제하는 값 저장
					if(out != 0) {
						num[p] = 0;
						k_count ++;
					}
					if(k_count == K) { //배열이 전부 0이되면 종료
						break;
					}
				}
			}
			if(k_count == K) { //배열이 전부 0이되면 종료
				break;
			}
		}
		System.out.println(out);
	}
}

 

풀이 설명

• 입력받은 N (2~N) 배열 만들기 
  • 인덱스 계산을 쉽게 하기 위해서 0,1 인덱스를 0으로 채워서 2~N인덱스에 2~N 수를 넣어줌
• 2~N까지 반복 - 배열 전체가 0이 될때까지
  • num[k]가 0이 아니라면 값 지워지지 않았다는 뜻
    • num[k]=0; 으로 값 지워줌
    • 지워줄때마다 count++ (K번째에 지우는 값을 출력해야하기 때문에 count가 K가 될때 반복문 종료, count 출력)
  • num[k]값을 out 변수에 저장해주었다 why? 이미 배열 값이 0이라면 이미 지워졌다는 의미이므로 count 증가할 필요 없음
    • 그러므로 out != 0일때 해당 값을 0으로 바꿔주고 카운트도 증가