[c/c++] 소수 판별하기

2^61-1 이라는 큰 수의 소수 여부를 판별하고, 소요 시간을 나타내는 코드를 작성하였다.

 

이때, 프로그램의 시간 복잡도를 줄이기 위해 제곱근을 사용하였다.

 

#include <iostream>
#include <math.h>
#include <time.h>
using namespace std;


int main() {
    clock_t start, end; 
    double result;

    // 시간 측정 시작
    start = clock();

    long long int n = (long long int)pow(2,61)-1;
    bool isPrime = true;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n%i == 0) {
            isPrime= false;
            break;
        }
    }

    if(isPrime) cout << "소수입니다";
    else    cout << "소수가 아닙니다";
    
    // 시간 측정 끝
    end = clock();
    result = (double)(end - start); 
    
    // 결과 출력 
    cout << "\nresult : " << result << " microseconds" << endl; 

    return 0;
}

 

처음 프로그램을 작성했을 때는, 2^61-1이 소수임에도 불구하고 "소수가 아닙니다"라는 문구가 출력 되었다.

 

잘못된 결과가 나왔던 이유는 pow 함수가 int를 반환하는 함수였기 때문이었다. 2^61-1은 int형 변수에는 담기지 않기 때문에 (long long int)로 형변환하는 과정이 필요했다.