[Algorithm] big O (25 days : Running Time and Complexity)

참고 hackerrank : 30 days of code : 25

#define IS_PRIME "Prime"

#define IS_NOT_PRIME "Not prime"

bool primeFactor(long no, long factor){

    // botbinoo@naver.com

    return ((no < factor*factor)? true : (no % factor!=0 ? primeFactor(no, factor+1) : false));

}

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   

    // botbinoo@naver.com

    // prime factor of hackerrank

    // Not prime or Prime

    int T;

    cin>>T;

    for(int inx=0; inx<T; inx++){

        long testNumber;

        cin>>testNumber;

        if(testNumber == 1){

            cout <<IS_NOT_PRIME<<"\n";

        } else {

            cout <<(primeFactor(testNumber, 2) ? IS_PRIME : IS_NOT_PRIME)<<"\n";

        }

    }

    return 0;

}

#

어려운 내용이 아니기에 간단하게 구현했다.