개발/코딩테스트
코드업(codeup.co.kr) 1542 : 함수로 prime 또는 composite 출력하기 해설 (C언어)
ensuta
2022. 11. 1. 15:23
728x90
반응형
문제 설명
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 하면 된다.
실제 계산을 할 때는 바빌로니아의 알고리즘이라는 근삿값을 구하는 계산을 통해 할 수 있다.
반응형