[프로그래머스 C++] 소수 만들기

문제 : 소수 만들기

문제 설명

 

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
• nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

---

입출력 예

nums	result
[1,2,3,4]	1
[1,2,7,6,4]	4

 

 분석

 배열에서 숫자 3개를 선택하는 방법은 3중 for문을 이용하면 된다. 또한 소수를 판단하는 부분은 에라토스테네스의 체를 이용하면 된다.

 

SKopp at German Wikipedia, CC BY-SA 3.0

 

 구현

using namespace std;

// 에라토스테네스의 채
bool cache[1000 + 999 + 998 +1];
void make_primenums(int n)
{
	for (size_t i = 2; i <= sqrt(n); i++)
	{
		if (!cache[i]) continue;

		for (size_t j = i * i; j <= n; j += i)
		{
			cache[j] = false;
		}
	}
}

int solution(vector<int> nums)
{
	int answer = 0;
	memset(cache, true, sizeof(cache));
	make_primenums(1000+999+998);

	for (size_t i = 0; i < nums.size() - 2; i++)
	{
		for (size_t j = i + 1; j < nums.size() - 1; j++)
		{
			for (size_t k = j + 1; k < nums.size(); k++)
			{
				if (cache[nums[i] + nums[j] + nums[k]]) answer++;
			}
		}
	}

	return answer;
}

int main()
{
	vector<int> tmp = { 1,6,4 };
	cout << solution(tmp); // 1
	return 0;
}