[C언어 코드업 문제풀이] CodeUp 1284 : 암호 해독

코드업 1284번 암호 해독 문제 풀이 해답입니다.

 

1. 문제 설명

 

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

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

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

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

 

 

2. 입력

 

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

 

3. 출력

 

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

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

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

 

4. 입력 예시

 

21

 

5. 출력 예시

 

3 7

 

6. 문제 풀이

 

#include<stdio.h>
#include "math.h"
 
int Fn(int n) {
    int i;
    if (n == 1) return 0;
    if (n == 2) return 1;
    if (n % 2 == 0)
        return 0;
    for (i = 3;i<=sqrt((float) n );i+=2) {
        if (n%i == 0) return 0;
    }
    return 1;
}
 
int main(){
    
    int number;
    scanf("%d",&number);
 
    int a,b;
    a = 0;
    b = 0;
    for(int i = 0; i<=number; i++){
        if(i == 0){continue;}
        else{
            if(number%i == 0){
                if(Fn(i)){
                    if(Fn(number/i)){
                        a = i;
                        b = number/i;
                        break;
                    }
                }
            }
        }
        
    }
    if(a != 0 && b!= 0){
        printf("%d %d",a,b);
    }
    else{
        printf("wrong number");
    }
    return 0;
 

 

입력된 값이 (소수)*(소수)로 이루어졌는지 판별하고 해당 소수들을 출력하는 문제입니다.

이 문제를 풀려면 소수를 판별해야 하는데 소수의 조건으로서

 

-소수는 1과 자신만을 약수로 갖고 있으며

-2를 제외한 다른 소수는 모두 홀 수 입니다.

 

또한    

for (i = 3;i<=sqrt((float) n );i+=2) {

        if (n%i == 0) return 0;

    }

 

처럼 입력값의 제곱근 보다 작은 홀수에 나누어 진다면(약수가 있다면) 이는 소수가 아닙니다.

 

이를 이용하여 for(int i = 0; i<=number; i++) 로 i를 증가시켜가며 

i가 소수일때 입력값과 나누게 됩니다.(if(number%i == 0))

 

나눈 값 또한 소수이게 되면 소수를 출력하고 프로그램은 종료됩니다.