5636 소수 부분 문자열

으으음 사실 구하다가 시간초과 날 것 같았는데 맞아버렸다.. 

 

일단 소수 구하는 부분이 O(NloglogN) 인데 입력이 10^5라 괜찮고

 

다음으로 문자열 안에 소수가 있는지 확인하는 부분이 문제였다. 

 

bool check[100005];

int main() {
    for (int i = 2; i * i <= 1e5; i++)
    {
        if (check[i])
            continue ;
        
        for (int j = (i * 2); j <= 1e5 ; j += i)
            check[j] = true;
    }
    
    int count = 0;
    for (int i = 2; i <= 1e5; i++)
    {
        if (!check[i])
            count++;
    }
    cout << count;
    
    return 0;
}

 

그래서 호다닥 10^5 이하의 소수가 몇 개인지 확인하는 코드를 짜봤다.

 

결과는 9592개가 나온다. 

 

최대 1000개의 테스트 케이스가 들어오고 각 테케 길이는 255인데 문자열 하나 당 9592개를 확인해야 한다. 

 

그럼 1000 * 255 * 9592 = 24억

 

으음.. 어찌저찌 잘 돌아갔구나

 

그렇구나.. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MAXN 1e5
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

bool check[100005];

void make_prime()
{
    for (int i = 2; i * i <= MAXN; i++)
    {
        if (check[i])
            continue ;
        
        for (int j = i * 2; j <= MAXN ; j += i)
            check[j] = true;
    }
}

void solve(string s)
{
    for (int i = MAXN; i >= 2; i--)
    {
        if (!check[i])
        {
            string tmp = to_string(i);
            if (s.find(tmp) != string::npos)
            {
                cout << tmp << endl;
                break ;
            }
        }
    }
}

int main() {
    make_prime();
    
    string s;
    while (cin >> s)
    {
        if (s[0] == '0' && s.size() == 1)
            break;
        solve(s);
    }
    
    return 0;
}