JUNGOL 실력키우기 2811 : 소수와 합성수

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

 

---

 

개념 자체는 쉽지만 시간을 줄이는데에 아이디어가 필요한 것 같네요... 저는 그냥 하다가 시간이 안 나와서 힌트보고 알았습니다.;

 

 

#include <iostream>
 
using namespace std;
 
bool IsPrime(int num);
 
int main(void)
{
    int num[5];
 
    for (int i = 0; i < 5; ++i)
        cin >> num[i];
 
    for (int i = 0; i < 5; ++i)
    {
        // 입력 값이 1이면 소수 검사를 하지 않는다.
        if (num[i] == 1)
        {
            cout << "number one" << endl;
            continue;
        }
        // 입력 값이 1 이외의 값이면 소수인지 검사를 한다.
        if (IsPrime(num[i]))
        {
            cout << "prime number" << endl;
        }
        else
        {
            cout << "composite number" << endl;
        }
    }
}
 
bool IsPrime(int num)
{
    // 2부터 num의 루트값 까지 진행하며 나눈다.
    // 이건 num = a * b 라면 작은 수로 나눠지면 큰 수로도 나눠지기 때문에
    // 작은 수 만 검사하는 것이다.
    for (int i = 2; i*i <= num; ++i)
        if (num % i == 0)    return false;
    return true;
}

 

 

JUNGOL) 문제은행) 실력키우기) 소수와 합성수