[5636] c++ 소수 부분 문자열

1. 문제 링크

https://www.acmicpc.net/problem/5636

5636번: 소수 부분 문자열

2. 풀이

1) 조건을 보면 1~100000(1e5) 사이의 소수를 구하는 문제이다.

   따라서 100000까지의 소수를 에라토스테네스의 체를 사용하여 구해준다.

 

2) 100000->1까지 for문을 돌리면서 소수이면서 s_number(입력)에 부분 문자열에 들어있는 수를 구한다.

 그 수가 부분 문자열 중 가장 큰 소수이다.

 

 

#include <iostream>
#include <string>
#define MAX 1e5

using namespace std;

bool not_prime_check[100002];

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	//에라토스테네스의 체-> 소수 체크하기
	not_prime_check[1] = true;
	for (int i = 2; i <= MAX; i++)
	{
		if (not_prime_check[i])
			continue;
		for (int j = 2; i*j <= MAX; j++)
		{
			not_prime_check[i*j] = true;
		}
	}
	string s_number;
	while (true) {
		cin >> s_number;
		if (s_number == "0")
			break;
		for (int i = MAX; i >=2; i--)
		{
			//소수 중에 s_number에 들어 있으면 그 수가 가장 큰 소수 부분 문자열이다.
			if (!not_prime_check[i]) {
				string s_temp = to_string(i);
				if (s_number.find(s_temp) != string::npos) {
					cout << s_temp << "\n";
					break;
				}
			}
		}


	}


	return 0;
}

 

알게 된 개념

string.find 함수로 문자열의 안에 부분 문자열을 찾을 수 있다.

string.find(str)에서 str을 찾으면 해당 문자가 위치한 주소 값을 반환하며, 찾지 못한다면 string::npos를 반환한다.

 

첫 번째 생각했던 방법

1) 문자열의 부분 문자열을 모두 구한다.

2) 가장 큰 수를 기준으로 에라토스테네스의 체를 적용하여 최대의 수를 구한다

=>당연히 시간 초과가 뜰 것 같음

3) 부분 문자열 중 2,3,5 간단하게 소수가 아닌 것들을 제거하고자 함. => 더러운 코드가 될 것 같음

=> 구글링함.

 

참조

1. 풀이 방법 

https://burningjeong.tistory.com/311 

2. stirng.find 함수

https://sweetnew.tistory.com/85