글 읽기 - 11653 소인수분해 c언어 시간초과

suanbo_frog 2년 전 0

어떻게 하면 시간을 줄일 수 있을까요?

#include <stdio.h>

int main(){
    int n, i, j, pn[1000000] = {0, }, pt = 0, sign = 0;
    
    scanf("%d", &n);
    
    for(i = 2; i <= n; i++){
        for(j = 2; j < i; j++){
            if(i % j == 0){
                sign++;
                break;
            }
        }
        if(sign == 0){
            pn[pt] = i;
            pt++;
        }
        sign = 0;
    }

    pt = 0;
    
    while(pn[pt] != 0){
        if(n % pn[pt] == 0){
            n /= pn[pt];
            printf("%d\n", pn[pt]);
        }
        else pt++;
    }
}

hyj4689 2년 전 0

이중 반복문 없이 해보세요. 충분히 할 수 있을거에요

amsminn 2년 전 0

O(sqrt(N))에 소인수 분해할수있는 방법이 있으니 알아보시면 좋을듯합니다

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

문제

문제

출처

ICPC

11653 소인수분해 c언어 시간초과

suanbo_frog 2년 전 0

hyj4689 2년 전 0

amsminn 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말