[Algorithm] 해커랭크 - Time Complexity: Primality

https://www.hackerrank.com/challenges/ctci-big-o/problem

주어진 수가 소수인지 아닌지 판별하되, O(sqrt(n)) 시간안에 답을 내야하는 문제다.

에라토스테네스의 체라는 방법을 알아보면, n이 소수인지 아닌지 판별하기 위해서는 sqrt(n) 이하의 수만 나눠보면 된다고 한다.

왜 sqrt(n)이하의 수만 나누어 보면 되는지는 포스트 http://makedotworld.tistory.com/13 를 참조하길 바란다.

코드는 아래와 같다.

void isPrime(int number)
{
    bool isprime = true;
    if(number == 1)
    {
        cout << "Not prime" << endl;
        return;
    }
    if(number%2==0)
    {
        if(number != 2)
        {
            cout << "Not prime" << endl;
            return;
        }
    }
    for (int i = 3; i*i <= number; i=i+2)
    {
        if(number%i == 0)
        {
            isprime = false;
            break;
        }
    }
    if(isprime)
    {
        cout << "Prime" << endl;
    }
    else
    {
        cout << "Not prime" << endl;
    }
}

풀이 시간 : 10분

풀이 중 문제점 :

1. 1인경우를 판별하지 않아 몇몇 케이스가 Fail이 나왔다.

2. 에라토스테네스의 체 개념을 다시 검색해 봤다. (백준 알고리즘 풀이를 하다 이미 개념을 숙지하고 있었는데 까먹음)