Prime Number

아래 코드는 기본적인 소수의 정의를 이용하여 구혔하였으나, 2 ~ (n-1) 까지 모두 확인이 필요하여 비효율적이다.

- 시간 복잡도 : O(n)

#include <iostream>
#include <string>
using namespace std;

bool isPrime(int n) {
    int i;

    for (i = 2; i < n; ++i) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

void main()
{
    int num;
    cin >> num;

    string answer = isPrime(num) == true ? "true" : "false";
    cout << "is Prime? - " << answer << endl;
}

소수를 구하기 위해서는 제곱근까지만 확인해보면 되기 때문에 아래와 같이 수정하여 개선할 수 있다.

- 시간 복잡도 : O(logn)

bool isPrime(int n) {
    int i;
    int sqrn = (int)sqrt(n);

    for (i = 2; i < sqrn; ++i) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}