백준 2023번 신기한 소수 문제풀이(C++)

백준 2023번 신기한 소수

아이디어

첫 시작은 항상 소수여야하고 뒤에 따라오는 수들은 항상 홀수여야 한다.

첫 시작 부분을 소수로 고정 시켜주고

for (const int num : {2, 3, 5, 7})
{
	// call back_tracking;
}

뒤에 따라오는 수들을 홀수로 해준다.

// fn -> backtracking
for (int i = 1; i < 10; i += 2)
{
	// num * 10 + i 가 소수 일 때만 진행
	// fn -> back_tracking, 만들어진 수로 자리 수가 맞을 때 까지 판별
}

소수가 맞는지 판별

// fn -> check(num)
for (int i = 2; i <= sqrt(num); i++)
{
	if (num % i == 0)
	{
			return true;
	}
}
return false;

문제풀이

#include<bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
bool check(const int num)
{
	for (int i = 2; i <= sqrt(num); i++)
	{
		if (num % i == 0)
		{
			return true;
		}
	}
	return false;
}
void back_tracking(const int n, const int idx, const int num)
{
	if (n <= idx)
	{
		cout << num << '\n';
		return;
	}
	for (int i = 1; i < 10; i += 2)
	{
		const int tmp = num * 10 + i;
		if (check(tmp)) { continue; }
		back_tracking(n, idx + 1, tmp);
	}
}
int main()
{
	FAST_IO;
	int n; cin >> n;
	for (const int num : {2, 3, 5, 7})
	{
		back_tracking(n, 1, num);
	}
	return 0;
}