백준1418번-K세준수(브론즈1)

출처 : https://www.acmicpc.net/problem/1418

1418번: K-세준수

문제풀이) 소인수 분해 한 약수중 가장 큰수를 기준으로 k보다 작은 수를 찾는 것이다.

에라토스테네스 체를 치는 원리를 이용해서 소수이면 소수의 배수들을 찾아 가면서 소인수의 약수의 크기를 자신으로 변경 해 준다.

#include <iostream>

#define MAX 100010

using namespace std;

int arr[MAX];

int main()
{
    int n,k;
    int cnt=0;
    cin >> n >> k;
    for(int i=2;i<=n;i++)
    {
        if(arr[i]) continue; //소수가 아니면 건너 뛰자
        for(int j=i;j<=n;j+=i)
        {
            arr[j]=max(arr[j],i);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(arr[i]<=k) cnt++;
    }
    cout << cnt;

    return 0;
}