[백준][2023][c++] 신기한 소수

신기한 소수 링크

[풀이]
주어진 자리수에 맞춰서 시작 수와 끝수까지의 모든 수가 prime인지를 확인하면 된다.
하지만 이렇게 할 시 시간 초과가 남으로 첫자리 수가 소수가 아니면 다음 첫자리수로 넘어가는 것을 구현했다. 첫자리 수뿐만 아니라 첫자리에서 두번째수가 소수가 아니면 두번째 수를 증가시키는 것을 구현했다. 세번째... 네번째 도....

[코드]

#include <iostream>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

int N;
int start, end_num;
vector<int> result;

int make_num(int n, int num, int num2) {
	//자리수에 맞추어 시작 그리고 끝 수 만드는 것 ex) N == 2 --> 100,999
	string result = "";
	result.append(to_string(num));
	n--;
	while (n) {
		result.append(to_string(num2));
		n--;
	}
	return stoi(result);
}

bool check_prime(string target) {
	//prime 이면 true, 아닐 시 false
	int num = stoi(target);
	for (int i = 2; i * i <= num; i++) {
		if (num % i == 0) return false;
	}
	if (num == 1) return false;
	return true;

}

void solve(int start, int end_num) {
	for (int num = start; num <= end_num; num++) {
		string num_str = to_string(num);
		if (num_str[0] == '1' || num_str[0] == '4' || num_str[0] == '6' || num_str[0] == '8' || num_str[0] == '9') {
			//시작이 1,4,6,8,9로 시작하는 것은 이미 소수가 아니어서 1xxx -> 2xxx로 넘어가야 함
			num += pow(10, N-1)-1;
			continue;
		}
		bool flag = true;
		for (int i = 1; i <= num_str.size(); i++) {
			string target = num_str.substr(0, i);
			flag = check_prime(target);
			if (!flag) {
				//cout << target << " "<<num_str<< " "<<num << " " << pow(10, N - i) << " ";
				num += (int)pow(10, N - i)-1;
				//cout << num << "\n";
				break;
				
			}
		}
		if (flag) result.push_back(num);
	}
}

void print_result() {
	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << "\n";
	}
}


int main() {
	cin >> N;
	start = make_num(N, 1,0);
	end_num = make_num(N, 9, 9);
	solve(start, end_num);
	print_result();
}

[총평]
시간 초과를 해결하는 logic을 만드는 것이 시간을 잡아 먹었다. dfs로 푸는 방법도 있던대 그것이 더 깔끔한 것 같다.
https://yabmoons.tistory.com/109