소수와 합성수 > 문제은행



실력키우기 수학

2811 : 소수와 합성수

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



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




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



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


3 10 1 55 127
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
bool isPrimeNaive(int n){
    if(n < 2) return false;      /// 1이하의 수는 소수가 아니다.(예외처리)
    for (int i=2; i < n; i++) {  /// 2부터 자신보다 작은 모든수로 나누어 본다.
        if (n % i == 0)
            return false;        /// 1과 자신 이외의 약수가 있으므로 소수가 아니다.
    }
    return true;                 /// 1과 자신 이외의 약수가 없으므로 소수이다.
}

///코드2
bool isPrime(int n){
    if(n < 2) return false;
    for (int i=2;  i <= n / i ; i++) { /// i*i <= n은 i*i에서 overflow 발생가능
        if (n % i == 0) return 0;
    }
    return 1;
}


int main() {
    ...
    if (n < 2) printf("number one\n");
    else if (isPrime(n)) printf("prime number\n");
    else printf("composite number\n");
    ...
}

[코드1 분석]
isPrime(int n)함수는 n이 소수이면 true를 아니면 false를 리턴한다.
2부터 n-1까지 수 중에서 약수가 발견되면 즉시 false를 리턴한다.
2부터 n-1까지 수 중에서 약수가 발견되지 않으면 tue를 리턴한다.

isPrime 함수는 다음과 같이 int형으로 선언하여 처리할 수도 있다.
int prime(int n) {
    if( n < 2) return 0;
    for (int i=2; i < n; i++) {
        if (n % i == 0)
            return 0;
    }
    return 1;
}

[코드1의 고찰]
위와 같이 처리하면 결과값은 나올 수 있지만 반복문을 2부터 입력받은 수까지 실행을 해야 하기 때문에
큰 수가 입력되면 시간이 초과될 수 있다.
시간을 줄이기 위해 약수를 구할 때 제곱근을 이용해 보자.
a * b = n (a > 1, b> 1)이라 할 때 a와 b는 n의 약수이다.
그러므로 a와 b중 작은 수 쪽만 확인해 보아도 n이 합성수임을 알 수 있는데
작은 수의 범위는 n의 제곱근 이하이다.
따라서 [코드2]같이 함수를 수정함으로써 시간을 획기적으로 줄일 수 있다.


[코드2 분석]
int sq = sqrt(n)라고 할 때,
(i <= n / i)는  결과적으로 (i <= sq) 와 같다.
 코드2는 코드1에서 i < n을 i <= n / 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.