[백준] 1418 K-세준수 - Java

 

 

 

에라토스테네스의 체를 이용해서 푸는 방식인데.. 문제에 맞게 잘 변형해서 푼 풀이를 가져와서 공부했다.

 

원래 방식대로면 시간 초과가 나기 쉬운데 상황에 알맞게 잘 변형해서 푼 좋은 풀이인 것 같다. 공부하자..

 

 

import java.util.*;
import java.io.*;
import java.math.*;

public class Main {				
		public static void main(String[] args) throws IOException {			
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	    				
			
			int N = Integer.parseInt(br.readLine());
			int K = Integer.parseInt(br.readLine());			
			int cnt = 0;

			int[] arr = new int[N+1];

			for(int i=2; i<N+1; i++){
				if(arr[i] != 0){
					continue;
				}

				for(int j=i; j<N+1; j=j+i){
					arr[j] = Math.max(arr[j], i);
				}
			}

			for(int i=1; i<N+1; i++){
				if(arr[i] <= K){
					cnt++;
				}				
			}

			for(int k : arr){
				System.out.print(k + " ");
			}
			System.out.println(cnt);
	}	
}