글 읽기 - 시간 초과

79brue 6년 전 0

시간을 절약할 방법

없을까요?

#include <stdio.h>
#include <stdbool.h>
bool prime(long long int n){
    for(long long int i=2; i<n/2; i++){
        if(n%i==0)
            return false;
    }
    return true;
}

int main(){
    long long int n; bool pr;
    scanf("%lld", &n);
    do{
        if(prime(n)){
            printf("%lld", n);
            return 0;
        }
        else{
            for(long long int i=2; i<n/2; i++){
                if(n%i==0&&prime(i)){
                    printf("%lld\n", i);
                    n/=i;
                    break;
                }
            }
        }
    }
    while(1);
}

baekjoon 6년 전 0

먼저, 어떤 수가 소수인지 아닌지 판별하려면 루트n까지만 포문을 돌리면 됩니다.

그리고, 이 방법으로는 시간 안에 문제를 풀 수 없어요.

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

문제

문제

출처

ICPC

시간 초과

79brue 6년 전 0

baekjoon 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말