소수 판별하기

소수를 판별하는 방법은 다양하게 존재하고 있습니다. 여기서는 크게 3가지 방법으로 소수를 구하는 방법을 찾아보겠습니다.

i) 임의의 정수를 입력했을때 나누어 떨어지지 않는 경우

임의의수 X에 대해 X를 2부터 X-1로 순서대로 나누어 떨어지는지 검사하면 알 수 있다.

나누어 떨어지는 경우가 나타나면 소수가 아닌 것이다.

#include <iostream>

#include <string>

using namespace std;

int main() {

    int x,i,j;

    cin >> x;  // 판별하기 위한 숫자 입력

    i = x-1;

    j = 2;

    while (1) {

        if (j <= i) {

            if( x % j == 0){

                cout <<" 소수 아니다" << endl;

                break;

            }else {

                j +=1;

            }

        }else {

            cout << "소수이다" << endl;

            break;

        }

    }

    return 0;

}

ii) 임의의 정수를 입력했을때 나누어 떨어지는 경우

임의의수 X에 대해 X를 2부터 X-1로 순서대로 나누어 떨어지는지 검사하면 알 수 있다.

나누어서 처음으로 나누어 떨어졌을 때 X와 같은 값이면 소수이다. 

#include <iostream>

#include <string>

using namespace std;

int main() {

    int x, y;

    

    cin >> x;

    y = 2;

    while (x % y != 0) {

        y++ ;

        

    }

    if ( x == y)

    {

        cout << "소수이다\n";

    }else{

        cout << "소수가 아니다.\n";

    }

}

iii) 제곱근을 이용하기

임의의수 X에 대해 X를 2부터 X의 제곱근까지 숫자로 나누었을때 떨어지는지 검사한다.

한번도 나누어 떨어지지 않으면 소수이고, 한번이라도 나누어 떨어지는 경우가 나타나면 소수가 아니다.

#include <iostream>

#include <math.h>

using namespace std;

int main() {

    int x,y;

    cin >> x;

    y=2;

    while (1) {

        if ( y <= sqrt(x)){

            if( x % y ==0){

                cout << "소수가 아니다 \n";

                break;

            } else

                y++;

        } else{

            cout << " 소수이다. \n";

            break;

        }

    }

    return 0;

}