글 읽기 - 50% 에서 시간초과가 뜨는데 원인이 무엇일까요?

girlera7 3년 전 0

50% 에서 시간초과가 뜨는데 원인이 무엇일까요?

#include<iostream>
#include<cmath>
typedef long long int ll;

using namespace std;

bool is_prime(ll target) {
    
    ll limit = int(pow(target, 0.5));
    for(ll candidate = 2; candidate <= limit; candidate++) {
       if(target % candidate == 0) {
           return false;
       }
    }
    
 
    return true;
}

bool is_prime(ll target, ll prime[65000], ll size) {
    ll limit = int(pow(target, 0.5));
        
    for(ll i = 0; i < size; i++) {
        if(prime[i] > limit) {
            break;
        }
        if(target % prime[i] == 0) {
            return false;
        }
    }
    
    return true;
    
}
int main() {
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll T;
    cin >> T;
    ll N;
    ll target;
    
    for(int i = 0; i < T; i++) {
        ll prime[65000];
        ll index = 0;
        cin >> N;
        target = N;
        ll limit = ll(pow((N + 1000), 0.5));
        
        for(ll j = 2; j <= limit; j++) {
            if(is_prime(j)) {
                prime[index] = j;
                index++;
            }
        }
        while (true) {
            if(is_prime(target, prime, index)) {
            cout << target;
             break;
        } else{
            target++;
        }
        }
        
    }
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

50% 에서 시간초과가 뜨는데 원인이 무엇일까요?

girlera7 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말