앳코더90 - 030 - K Factors（★5）

https://atcoder.jp/contests/typical90/tasks/typical90_ad

030 - K Factors（★5）

 

2이상의 N이하의 정수 중에서 소인수가 K개이상인 정수의 개수를 구하라.

 

난이도가 왜 별 5개 짜리문제인지는 모르겠다. 난이도만 보고 수학적인 뭔가를 써야 되나 싶었다. 우선 각 N마다 소인수분해를 해서 저장하는 방식이 문제의 의도는 아닐것이다. 예전에 이런 비슷한 문제를 백준에서 본적이 있어서 쉽게 접근할 수 있었던 것 같다. 에라토스테네스의 체를 사용하는 테크닉이다. 소인수라는 것은 결국 약수와 같은 개념이기 때문이다. 

 

아래 코드처럼 역으로 인수에 해당하는 값들에 더해준다. 

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
#include <numeric>
#include <random>
#include <iostream>
#include <unordered_map>
#include <atcoder/all>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back

using namespace std;
using namespace atcoder;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;

const int INF = 2000000000;
const double pi = 3.14159265358979;
const int MOD = 100000;

void yesno(bool a)
{
	if (a)
		cout << "YES\n";
	else
		cout << "NO\n";
}

int N, K;
int arr[10000002];
int ans;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> K;

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

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

	for (int i = 2;i <= N;i++)
	{
		if (arr[i] >= K)
			ans++;
	}

	cout << ans;

	return 0;
}