[Code Up] 1284번 : 암호 해독

난이도  ⭐️⭐️⭐️⭐️

문제 설명

암호 해독

두 소수의 곱을 암호로 사용하는 알고리즘은 큰 수의 소인수분해가 어렵기 때문에 안전하다고 알려져 있다.

그렇지만, 만약 두 소수를 잊어버리면 어떻게 될까? 굉장히 난감할 것이다.

이에 대비해 어떤 수(n)가 입력되면 두 소수의 곱으로 나타낼 수 있으면 두 소수를 오름차순으로 출력하고,

그렇지 않으면 "wrong number"를 출력하는 프로그램을 작성하시오.

입력

어떤 수 n이 입력된다.(단, 1 <=n <=10,000,000)

출력

n을 두 소수의 곱으로 나타낼 수 있으면 두 수를 오름차순으로 출력한다.

(단, 가능한 소수 중 가장 작은 소수와의 곱으로 나타낸다.)

하고, 그렇지 않으면 "wrong number"를 출력한다.

[입력 예시]

21

[출력 예시]

3 7

문제 풀이

이 문제가 어렵게 느껴지는 이유는 n을 두 소수의 곱으로 나타내야 함과 동시에 두 수를 오름차순으로 나타내야 한다는 것이다.

이때 가장 중요한 점은 가능한 소수 중 가장 작은 소수와의 곱으로 나타내야 한다.

이러한 문제는 소인수분해로 접근한다!

 

입력받은 n값이 두 소수의 곱으로 나타낼 수 있는지 판단하기 위해서는 소인수분해를 했을 때 1과 n을 제외한 소인수가 2개이어야 한다. 이때 2는 인수가 1과 2로 소수가 아닌 1이 소인수임에 주의한다.

 

입력받은 값을 a라고 하면 a를 가지고 약분을 시작한다. 이때 fac이라는 약분 변수를 선언하고 2로 초기화한다. 2로 초기화한 이유는 소인수분해의 가장 처음 값이기 때문이다. fac으로 나머지가 0인 경우는 a를 fac 변수의 값으로 나눈다. 여기까지도 일반적 소인수분해라고 생각하면 된다. a가 fac으로 나눠지지 않는 경우는 fac 변수를 증가시키며 fac 변수가 a보다 켜지만 반복을 종료한다.

int a,ipt,fac=2,cnt=0;
    scanf("%d",&a);ipt=a;
    while(a>fac){
        if(a%fac == 0){cnt ++;a/=fac;}
        else fac++;
    }

이때 위의 변수 중 ipt와 cnt의 기능은 아래와 같다.

[ipt]

반복을 연산하면서 바뀌는 a의 값을 저장한다. 저장하는 이유는 입력된 값이 두 소수의 곱으로 나타낼 수 있을 경우 입력된 소수의 값을 이용해 두 소수를 출력하기 위함이다.

[cnt]

cnt의 기능은 소인수의 개수를 찾는 것이다. 위 코드의 조건문으로 보면 a가 fac으로 나눌 때의 나머지가 0인 경우, 즉 a가 fac으로 나눠지면 소인수이라는 뜻이며 이때 cnt값에 1을 추가하는 것을 볼 수 있다.

 

21을 예로 들면 21을 나눌 때 나머지가 0이 되는 3이 될 때까지 fac은 증가하며 fac의 값이 3이 될 경우 cnt의 값은 1이 되고, a의 값은 7이 된다. 이때 a의 값인 7이 fac으로 나눠지려면 fac은 7이 될 때까지 증가해야 하지만 fac이 7이 되는 순간 a와 같아지므로 반복을 종료된다.

따라서 반복이 끝나면 a의 값은 7, fac의 값은 7로 종료된다.

 

반복을 통해 a와 fac의 값을 알 수 있다. 하지만 우리가 원하는 출력하고자 하는 값은 두 소수를 나타내는 것이므로 여기서 초기 a의 값을 저장한 ipt가 필요한 것이다. fac보다 작은 소수의 값은 당연히 ipt / fac 이 되는 것이다.

정답 코드

#include<stdio.h>
int main(){
    int a,ipt,fac=2,cnt=0;
    scanf("%d",&a);ipt=a;
    while(a>fac){
        if(a%fac == 0){cnt ++;a/=fac;}
        else fac++;
    }
    if(cnt == 1)printf("%d %d",ipt/fac,fac);
    else printf("wrong number");
}