소수와 합성수 > 문제은행



2811 : 소수와 합성수

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
1199 회   
시도횟수
3066 회   

문제

소수(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

Hint!

소수(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]

 

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

 

 

[코드2 ]

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool isPrime(int n)
{
    if(n < 2return false;
 
    for (int i=2; i <= n / i ; i++)
    {
        /// i*i <= n은 i*i에서 overflow 발생가능
        if (n % i == 0return 0;
    }
    return 1;
}
 
int main()
{
    ...
    
    if (n < 2printf("number one\n");
    else if (isPrime(n)) printf("prime number\n");
    else printf("composite number\n");
 
    ...
}
 
cs

 

 

[코드1 분석] 

isPrime(int n)함수는 n이 소수이면 true를 아니면 false를 리턴한다. 

2부터 n-1까지 수 중에서 약수가 발견되면 즉시 false를 리턴한다. 

2부터 n-1까지 수 중에서 약수가 발견되지 않으면 tue를 리턴한다. 

isPrime 함수는 다음과 같이 int형으로 선언하여 처리할 수도 있다.

 

1
2
3
4
5
6
7
8
9
10
int prime(int n)
{
    if( n < 2return 0;
    for (int i=2; i < n; i++)
    {
        if (n % i == 0return 0;
    }
    return 1;
}
 
cs

 

 

[코드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

수학알고리즘

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP