뒤집은 소수

N개의 자연수가 입력되면 각 자연수를 뒤집은 후, 그 뒤집은 수가 소수이면 그 수를 출력하는 프로그램 작성!

ex) 32가 입력된 경우, 이를 뒤집으면 23이고 23은 소수이므로 출력

*뒤집는 함수 reverse(x)와 소수인지를 판별하는 함수 isPrime(x)을 반드시 작성

 

입력예시)

5

32 55 62 3700 250

 

출력예시)

23 73

---

내가 처음에 쓴 코드

def reverse(x):
    x = str(x)
    return int(x[::-1])

def isPrime(x):
    for i in range(2,x):
        if x%i == 0:
            return False
    return True

N = int(input())
inputLst = list(map(int, input().split()))

for x in inputLst:
    reversedNum = reverse(x)
    if isPrime(reversedNum):
        print(reversedNum, end=' ')

---

모범답안

def reverse(x):
    res = 0
    while x > 0:
        t = x % 10
        res = res * 10 + t
        x = x//10
    return res

def isPrime(x):
    if x == 1:
        return False
    for i in range(2, x//2+1):
        if x % i == 0:
            return False
    else:
        return True


n = int(input())
a = list(map(int, input().split()))

for x in a:
    tmp = reverse(x)
    if isPrime(tmp):
        print(tmp, end=' ')

---

모범답안 보고 느낀점

 

1. 우선 reverse()의 접근 방식 자체가 나와 너무 다름
난 우선 문자열로 바꾸고 슬라이싱을 통해 거꾸로 쓴 뒤 다시 정수로 리턴하는 
방식을 취했는데, 보시다시피 모범답안은 숫자 자체로 임시 변수 t를 생성해서 
식을 만들고, 자릿수가 거꾸로 된 res를 리턴함
하지만 나는 자연수를 뒤집어야 한다고 할 때, 저 식을 생각해낼 자신이
전혀 없는걸?!!!!

2. 소수 판별 isPrime()
숫자의 모든 약수를 알아보는 목적이 아니라면 isPrime에서 반복문을 x까지 돌 필요는 없었다.
어떤 수가 소수가 아니라면, 그의 약수들은 대칭성을 띄기 때문임
예를들어 16의 경우
1 * 16
2 * 8 
4 * 4
8 * 2
16 * 1
이런식으로 곱셈 쌍이 생성되면서 대칭성을 띈다

근데? 모범답안에선 대칭성을 고려하여 판별하고자 하는 숫자의 절반을 탐색했다 (x//2+1)
하지만 좀 더 생각해보면 특정 숫자의 제곱근까지만 확인해도 충분하다.

왜? 그 숫자가 소수가 아니라면 대칭을 이루는 두 약수 중 하나는 반드시
sqrt(x)보다 작거나 같기때문!

만약 x의 약수가 a,b라고 했을때 
a,b모두 sqrt(x)보다 크다면
a > sqrt(x) 그리고 b > sqrt(x)
그러면 a * b = x > sqrt(x) * sqrt(x) = x
즉, x > x가 되어버려 모순이다.

따라서 제곱근까지만 확인해도 충분히 숫자가 소수인지 아닌지 판별할 수 있을것.

3. 아, 그리고 isPrime에 1이 들어올 수 있다는 생각을 깜빡함 ㅜ
넘 초딩같은 실수기때문에 길게 말하지 말자

---

다시 작성해보기

from math import sqrt

def reverse(x):
    x = str(x)
    return int(x[::-1])

def isPrime(x):
    if x < 2:
        return False
    for i in range(2, int(sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True

n = int(input())
numLst = list(map(int, input().split()))

for x in numLst:
    reversedNum = reverse(x)
    if isPrime(reversedNum):
        print(reversedNum, end = ' ')