소수인지 판단하는 법 c++ 코드

소수란?

소수는 1이 아닌 자연수 중에서 1과 자기 자신 이외의 약수를 갖지 않는 수를 뜻한다.

문제 예시

31이 소수인지를 구하시오

팁

루트를 이용하여 시간을 반으로 줄인다.

소수가 아닌 수는 곱셈으로 표시되는 숫자이며 어차피 반대편수의 반복이기 때문이다. 

예를 들면

12의 경우 

2 6 / 3 4 / 4 3 / 6 2

와 같은 식의 약수의 곱이 안오는데 3 4 이후로는 앞에 나온 숫자를 자리만 바꾸어 반복하는 것이기 때문이다.

풀이

C++ 소스 코드

#include <iostream>

#include <math.h>

// 소수인지 판단

bool primeNumber(int n){

    if(n<2){

        return false;

    }

    int num = sqrt(n);

    for (int i = 2; i<= num; i++){

        if (n % i ==0){

            return false;

        }

    }

    return true;

}

int main() {

    int N = 31;

    bool result = primeNumber(N);

    if(result){

        std::cout << "소수\n";

    } else {

        std::cout << "소수 아님\n";

    }

    return 0;

}