백준 1418 K-세준수 자바로 풀어 본 짧은 글

1418번 K-세준수

N까지의 값을 입력받아서 각 수의 소인수분해를 통해 소인수를 받고 해당 소인수의 최댓값을 입력받은 K와 비교해 카운트한 수를 출력

-----

hint

각 소인수를 hashMap에 저장 이후 맥스값 출력

-----

Solution

실행시간 - 3496ms

import java.util.*;
import java.io.*;
// 1 2 3 4 5 6 7 8 9 10
// 1 2 3 2 5 3 7 2 3 5
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[] a = new int[n+1];
        HashMap<Integer, Integer> hs = new HashMap<Integer, Integer>(n+1);
        
        for(int i = 0; i <= n; i++){
            a[i] = i;
            hs.put(i,0);//해시맵 초기화
        }
        
        //1은 되니까 배제
        for(int i = 2; i <= n; i++){//2부터 n까지의 소인수들을 저장
            int soinsu = a[i];
            for(int j = 2; j <= soinsu; j++){
                while(soinsu % j == 0){ 
                    soinsu /= j;
                    hs.put(i, j);
                }
                // 소인수분해 한 값들중에서 max값을 해당 hs에 집어넣는다.
            }
        }
        
        int count = 0;
        for(int i = 1; i < a.length; i++){
            if(hs.get(i) <= k){
                count++;
            }
        }
        System.out.println(count);
    }
}

직접 무식하게 푼거라 효율이 매우 좋지 않음...