(코드업) 1284-암호해독

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

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

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

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

 

#include <stdio.h>

int main() {
int a, b, c=1, d=1;
  scanf("%d", &a);             //1
  if(a<=2)                     //2
  printf("wrong number");
  
  
    for(int i=2; i<a; i++){    //3, 4
        if(a%i==0){
          b=i;
          for(int j=2; j<b; j++){
            if(b%j == 0)
             c++;     
              }
          if(c<2){
            d=d*b;
            if(d==a){
          printf("%d %d", a/b, b);
                return 0;
            }
          }
          else{
            printf("wrong number");
          return 0;}
          }
          
    }
    for(int i=2; i<a; i++){       //5
  if(a%i != 0){
  printf("wrong number"); return 0;}
  }  
    return 0;
    }

순서

1. 숫자를 변수 a에 입력받는다.

 

2.  2 이하인 수는 입력받은 수를 두 소수의 곱으로 나타낼수 없으므로 wrong number를 출력하고 코드를 종료한다.

 

3. a의 소수를 구하고 그 소수끼리 곱했을때 a가 나온다면 그 소수를 출력하고 코드를 종료한다.

소수인 숫자 b를 전에 저장해둔 소수 b와 곱했을때 a가 나온다면 b를 출력하고 a/b는 또 다른 소수이기 때문에 더 작은 숫자인 a/b를 먼저 출력후 b를 출력한다.

 

4. a의 소수끼리 곱해도 a가 나오지 않는다면 wrong number를 출력하고 코드를 종료한다.

     

5. 위 3, 4번은 a가 소수가 아니라는 가정하에 만든 식이기 때문에 a가 소수이면 wrong number를 실행하고 코드를 종료하게 한다.