소수와 합성수 > 문제은행

본문 바로가기


실력키우기 수학

2811 : 소수와 합성수

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 665 회    시도횟수: 1830 회   



소수(prime number)란 1보다 큰 자연수 중 1과 자기 자신 두 개만을 약수로 갖는 수를 말한다.
합성수(composite number)란 1보다 큰 자연수 중 소수가 아닌 수를 말하며 3개 이상의 약수를 갖는다.
1은 소수도 합성수도 아니다.
5개의 자연수를 입력받아 소수인지 합성수인지를 판단하는 프로그램을 작성하시오.


10억 이하의 자연수 5개가 공백으로 구분되어 주어진다.


입력된 순서대로 한 줄에 한 개씩 소수이면 "prime number", 합성수이면 "composite number", 소수도 합성수도 아니면 "number one"이라고 출력한다.

[Copy]
3 10 1 55 127
[Copy]
prime number
composite number
number one
composite number
prime number


소수(prime number)란?
 문제에서 주어진 바와 같이 약수가 1과 자기 자신 두 개만을 갖는 자연수를 소수라 한다. 
 20이하의 소수는 8개(2, 3, 5, 7, 11, 13, 17, 19)이다.

합성수란(composite number)?
1과 자기 자신 이외에 다른 약수를 갖는 수, 즉 약수가 3개 이상인 자연수를 말한다. 
 20이하의 합성수는 11개(4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20)이다.

1은 소수도 합성수도 아니다.

코드1
 01  int prime(int x)
 02  {
 03      int i;
 04      for (i=2; i < x; i++) {       // 2부터 자신보다 작은 모든수
 05          if (x % i == 0) return 0; // 나누어 떨어지면(약수이면) 소수가 아니므로 0을 리턴한다.
 06      }
 07      return 1; // for 문이 끝날때까지 약수가 없으면 소수이므로 1을 리턴한다.
 08   }

09  int main()
 10  {
 11      ...
 12       for (i=0; i < 5; i++) {
 13           if (a[i] < 2) printf("number one\n");
 14           else if (prime(a[i])==1) printf("prime number\n");
 15           else printf("composite number\n");
 16       }
 17       ....
 18   }

코드분석
prime(int x) 함수는 자연수를 전달받아 x에 저장한 후 x가 소수이면 1을 아니면 0을 리턴하는 함수이다. 2부터 x-1까지에서 차례대로 약수인지 확인하여 약수가 발견되는 즉시 0을 리턴한다. 반복문이 끝날때까지 리턴이 되지 않는다면 약수가 없는 것이므로 1을 리턴한다.
   
 prime 함수는 다음과 같이 bool형으로 선언하여 처리할 수도 있다.
 01   bool prime(int x)
 02   {
 03       int i;
 04       for (i=2; i < x; i++) {       
 05           if (x % i == 0) return false;
 06       }
 07       return true; 
 08   }

위와 같이 처리하면 결과값은 나올 수 있지만 반복문을 2부터 입력받은 수까지 실행을 해 보아야 하기 때문에 큰 수가 입력되면 시간이 초과될 수 있다.
 시간을 줄이기 위해 약수를 구할 때 익혀두었던 제곱근을 이용해 보자.
 a * b = x라 할 때 a와 b는 x의 약수이다. 그러므로 a와 b중 작은수 쪽만 확인해 보아도 소수인지 아닌지를 판단할 수 있다. 작은 수의 범위는 이하이다.
 따라서 아래와 같이 함수를 수정함으로써 시간을 획기적으로 줄일 수 있다.

코드2
01   int prime(int x)
 02   {
 03       int i;
 04       for (i=2; i*i <= x; i++) {       
 05           if (x % i == 0) return 0; 
 06       }
 07       return 1; 
 08   }

코드분석 
(i * i <= x) 이것은 결과적으로 (i <= sqrt(x)) 와 같다. (양의 정수 부등식에서 양변을 제곱 해도 식은 성립한다.)
 코드2는 코드1에서 i를 i*i로 바꾼 것 뿐이지만 시간은 획기적으로 줄어들게 된다. 만약 입력된 값이 1억이라면 앞의 코드에서는 반복문을 1억번 실행해야 하지만 이 코드에서는 1만번만 실행하면 되므로 시간이 1/10000로 단축되는 것이다.


출처 : jungol



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.