문제

n이 입력(0 < k < n ≤ 2^31)되면 k를 빼서 제곱수를 만들 수 있는 k를 구하고, 그 제곱수에 루트를 씌운 수(제곱근) t를 구하여라

이 때 가장 작은 k를 출력한다.

IO example : 34 입력 → 출력 9 5

풀이

#include <stdio.h>
int main(){
    int a;
    scanf("%d",&a);
    if(a==1) return 0;
    for(int b=2;b<=a;b++){
        if(a%b==0){
            a=a/b;
            printf("%d\\n",b);
            b=1;
        }
    }
    return 0;
}

입력되는 n의 값을 a에 int로 저장 하고, n의 값이 1이라면 아무것도 출력하지 않고 종료해야 하므로, if(a==1) return 0; 로 처리합니다.

2부터 시작하여 a 이하가 될 때까지 1씩 증가하면서 반복합니다. b는 a를 나눌 수 있는지 확인하는 데 사용됩니다.

if(a%b==0)는, 만약 a가 b로 나누어 떨어진다면, a=a/b;로 a를 b로 나눈 값을 a에 다시 저장합니다. 이는 a의 소인수를 하나 제거하는 효과가 있습니다.

printf("%d\n",b); 로 현재의 소인수 b를 출력하고, b=1;로 b를 1로 재설정합니다.

for문이 끝나면 프로그램을 종료합니다.