[마이다스챌린지2017예선] 마이다스수(소수구하기)

마이다스수 문제 (MidasNumber)

“마이다스수”는 어떤 자연수의 소인수중 최대값이 M보다 크지 않은 수를 의미합니다. 여기서 소인수란 주어진 자연수를 나누어 떨어뜨리는 약수 중에서 소수인 약수를 말합니다.

1보다 크고 N보다 작거나 같은 자연수 중에 “마이다스수”가 총 몇 개인지 구하는 프로그램을 작성하십시오.

예를 들어, N이 10이고 M이 3인 경우 소인수의 최대값이 3보다 작거나 같은 수들은 2, 3, 4, 6, 8, 9 로 “마이다스수”는 총 6개 입니다.

입력

입력은 표준 입력(stdin)으로 주어지며

첫째 줄에 N, 둘째 줄에 M이 주어진다. N은 100,000보다 작거나 같은 자연수이고, M은 100보다 작거나 같은 자연수입니다.

출력

출력은 표준 출력(stdout)으로 이루어집니다.

첫째 줄에 N보다 작거나 같은 “마이다스수”가 몇 개인지 출력합니다.

입력예)

10 3

출력예)

6

#include <iostream>
#include <vector>
using namespace std;

vector<int> GetPrimes(int num) //num까지의 소수 구하기
{
	int *arr = new int[num + 1];
	for (int i = 2; i <= num; i++)
		arr[i] = i;

	vector<int> retPrimes;
	for (int i = 2; i <= num; i++)	
	{
		if (arr[i] == 0)
			continue;

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

	for (int i = 2; i <= num; i++)
	{
		if (arr[i] != 0)
			retPrimes.push_back(arr[i]);
	}
	delete arr;
	return retPrimes;
}

int main()
{
	int N, M;
	cin >> N;
	cin >> M;	//M보다 작은 소수

	vector<int> primes = GetPrimes(M);

	int count = 0;
	for (int i = 2; i < N; i++)
	{
		for (int j : primes)
		{
			if (i%j == 0)
			{
				count++;
				break;
			}
		}
	}
	cout << count;
	return 0;
}