글 읽기 - 시간초과

dongyun9501 1년 전 0

제곱처리를 해줘서 시간을 줄였는데도 시간초과에러가 뜨네요.. 더 시간을 줄일 수 있는방법은 없을까요?

#include <stdio.h>
#include <math.h>
int main() {
    int n;
    int cnt=0;
  int cnt1=0;
    scanf("%d",&n);
    if(n==1)
    {
      return 0;
    }
    
    for(int k=2; k<=n; k++)
    {
      if(n==1)
      {
        break;
      }
     for(int i=2; i*i<=k; i++)
          {
            if(k%i==0)
            {
            cnt++;
              break;
            }
          }
       
          if(cnt==0)
          {
             while(1)
                {
                  if(n%k!=0)
                  {
                    break;
                  }
                  n=n/k;
                  cnt1++;
                  
                }
  
              
            
            for(int i=0; i<cnt1; i++)
        {
          printf("%d\n",k);
        }
          }
     
      cnt1=0;
      cnt=0;
      
    }
    return 0;
}

zenith82114 1년 전 0

루프가 하나만 있어도 충분할 거 같은데 k루프와 i루프가 있는 이유를 설명해 주실 수 있나요?

dongyun9501 1년 전 0

k루프는 가장작은 소수부터 구하기 위해 2부터 돌린 루프이고 i루프는 2부터 시작한 k를 소수인지 검사하기 위해서 만든 루프입니다.

zenith82114 1년 전 0

30~39줄에 n이 k로 안 나눠질 때까지 나누는 부분이 있죠?

k가 처음에 2니까 2로 최대한 나누고, 그 다음 3으로 최대한 나눴다고 칩시다.

그 다음 k는 4인데, 앞에서 2로 끝까지 나눴으니까 당연히 4로 안 나눠질 겁니다.

5, 6, 7... 계속 생각해보시면 소수가 아니면 자동으로 걸러지기 때문에

소수인지 직접 판단할 필요가 없다는 걸 알 수 있습니다.

dongyun9501 1년 전 0

i루프지우니까 시간초과도 해결되고 답도 맞았네요!! 감사합니다 고수님!!

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

문제

문제

출처

ICPC

시간초과

dongyun9501 1년 전 0

zenith82114 1년 전 0

dongyun9501 1년 전 0

zenith82114 1년 전 0

dongyun9501 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말