코드업(codeup.co.kr) 1542 : 함수로 prime 또는 composite 출력하기 해설 (C언어)

문제 설명

prime 또는 composite 중 하나를 출력하시오.

단, 함수형 문제이므로 함수 f()만 작성하시오.

 

 

입력

int 형 자연수(n)가 입력된다.
(2 <= n <= 1000)

줄력

소수(prime)가 입력되면 prime, 합성수(composite)가 입력되면 composite 를 출력한다.

입력 예시msp

997

출력 예시

prime

 

해설

#include <stdio.h>

int n;

//O(n) 의 time complex 를 가져 좋지않은 알고리즘이지만, 
//이 문제 한정으로 사용해야마 풀수 있다.
void f(int n)
{
    int a = 0;

    for(int i = 1; i <= n; ++i) if(n % i == 0) ++a;

    if(2 == a) printf("prime");
    else printf("composite");
}

int main()
{
  scanf("%d", &n);
  f(n);
  return 0;
}

자연수를 1 부터 표적 숫자까지 하나씩 나눠보는 알고리즘이다.

i 는 1 부터 n 과 같아 질 때 까지 커지고

한 번 커질 때 마다 n 에 나눠 본다.

나머지가 0 이라면 나누어떨어진 것으로, i는 n의 약수가 된다. 그러면 n은 더이상 소수가 아니게 된다.

 

입력받은 숫자보다 크면 양의 제곱근의 기수가 더 커지기 때문에 따지지 않는다.

 

O(n) 의 time complex 를 가져 좋지않은 알고리즘이지만, 
이 문제 한정으로 사용해야만 풀 수 있다.

 

이 문제는 실제 근삿값을 구하기 보단 어림잡은 기수만을 return 하면 된다.

 

실제 계산을 할 때는 바빌로니아의 알고리즘이라는 근삿값을 구하는 계산을 통해 할 수 있다.