[백준 1418번] K-세준수

문제링크 : https://www.acmicpc.net/problem/1418

#include <bits/stdc++.h>
using namespace std;

int arr[100001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;

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

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

    cout << cnt;

    return 0;
}

 

입력받은 N을 토대로, 2~N까지 값에 대해 소인수 값을 체크해준다.

해당 j 및 j의 배수에 대해 현재 소인수 i를 모두 넣어준다.

이를 반복하며, ~N까지 모든 소인수를 갱신하며 소인수 중 최대값을 저장하게 된다.

 

이후에 해당 값들을 다시 순회하며 K보다 크지 않은 경우에 카운팅후 출력하면 된다.