[C++] 뒤집은 소수

[목적]

N개의 자연수를 입력 받은 후 수를 하나씩 뒤집어 그 수가 소수이면 출력한다.

 

[입력 예제]

5
32 55 62 3700 250

 

[출력 예제]

23 73

입력 받고 싶은 개수를 입력 한 후, 여기선 '5'개를 입력받는다 하였기에 총 '5'개의 숫자를 입력받는다.

그 후, 숫자를 뒤집어 해당 수가 소수이면 출력하는데 여기선 '32'와 '3700'을 뒤집었을 때 '23'과 '73'(앞자리 0은 무시)으로 두 수는 소수이기에 '23'과 '73'을 출력한다.

 

---

[코드 (Visual Studio2019)]

#include <iostream>
#include <string>

using namespace std;
bool isPrime(int x) {

    if (x == 1) return false;

    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

int reverse(int x) {

    string str = to_string(x);
    reverse(str.begin(), str.end());
    int num = stoi(str);
    if ((isPrime(num)) == true) cout << num << " ";

    return 0;
}


int main(void) {

    int cnt, num;

    cin >> cnt;

    for (int i = 1; i <= cnt; i++) {
        cin >> num;
        reverse(num);
    }

    return 0;
}

isPrime 함수는 소수인지 판별해주는 함수이다.

1은 소수가 아니니 무조건 false를 return하고, 그 외에 숫자는 1을 모두 약수로 가지기에 for문은 2부터 시작한다.

시간 복잡도를 위해 i * i가 입력받은 숫자보다 작거나 같을때까지만 반복해준다.

 

예제) x = 25

i	i * i	x % i
2	4	2
3	9	3
4	16	4
5	25	0

i가 5일 때 '%'연산을 한 값이 0이 나와 소수가 아니라 판별되어 false를 return한다.

 

예제2) x =7

i	i * i	x % i
2	4	2
3	9	----

7은 1과 자기자신만을 갖는 소수이다.

이때 2부터 7까지 for문을 돌리는건 시간 낭비가 될 수 있다.

그래서 i * i연산을 통해 반보다 작은 숫자를 돌려 범위를 벗어나게 되면 for문을 나가게 되고 true가 반환되도록 하였다.

 

[실행결과]

[코드 (DevC++)]

Dev는 GCC컴파일러를 사용하기에 to_string과 stoi같은 함수를 사용할 수 없다.

컴파일러를 C++11로 바꿀 수 있지만 컴퓨터의 문제인지.. 돌아가지 않는다...

아래 코드는 reverse함수를 수정한 코드이다.

#include <iostream>
#include <string>

using namespace std;

int reverse(int x) {

    int res=0, tmp;
    while(x>0){
        tmp=x%10;
        res=res*10+tmp;
        x=x/10;
    }
    return res;
}

bool isPrime(int x) {

    if (x == 1) return false;

    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

int main(void) {

    int cnt, num, tmp;

    cin >> cnt;

    for (int i = 1; i <= cnt; i++) {
		cin >> num;
        tmp = reverse(num);
        if(isPrime(tmp)) cout << tmp << " ";
    }

    return 0;
}