백준 [실버2] 10859 뒤집어진 소수

https://www.acmicpc.net/problem/10859

 

접근 방식

소수를 찾기 위해서는 먼저 해당하는 수의 약수를 모두 구해서 약수의 총합이 2개라면 소수라고 판결을 내린다 -> O(n)

 

N의 약수 쌍을 보면 둘중의 작은 값은 무조건 sqrt(N)의 범위 안에 존재한다

12 = > (1,12), (2,6), (3,4)

소수찾기는 모든 수를 보지 않고 sqrt(n) 만큼의 수만 확인해도 소수를 판별 할 수 있다

 

즉 위와 같은 방식으로 O(n)이 아닌 O(sqrt(n)) 만큼의 시간 복잡도로 줄 일 수 있다

 

숫자를 reverse 할때는 숫자를 문자열로 바꿔서 더해주는 방식으로 진행했고

3,4,7은 뒤집었을때 숫자가 아니므로 소수 1이라는 값을 가지도록 강제했다

 

 

소스코드

처음에 시도한 코드 -> 시간초과

 

number = int(input())
reverse = ""

def isPrime(n):

    n = int(n)

    if n == 1 or n == 0:
        return False

    for i in range(2, n + 1):
        if i * i > n:
            break

        if n % i == 0:
            return False

    return True

temp = number

while temp / 10 != 0:
    n = temp % 10
    if n == 6:
        reverse += "9"
    elif n == 9:
        reverse += "6"
    elif n == 3 or n == 4 or n == 7:
        reverse = 1
        break
    else :
        reverse+=str(n)

    temp //= 10



if(isPrime(number) and isPrime(reverse)):
    print('yes')
else:
    print('no')

 

 

소수를 판별하는 isPrime()함수에서 i*i를 할때, 숫자가 클때 제곱하는데에 오랜 시간이 걸린다고 판단해서

for문에서 sqrt를 사용하게 끔 아래와 같이 바꿔주었더니 통과했다

 

수정된 코드

 

number = int(input())
reverse = ""

def isPrime(n):

    n = int(n)

    if n == 1 or n == 0:
        return False

    for i in range(2, int(n**0.5)+1):

        if n % i == 0:
            return False

    return True

temp = number

while temp / 10 != 0:
    n = temp % 10
    if n == 6:
        reverse += "9"
    elif n == 9:
        reverse += "6"
    elif n == 3 or n == 4 or n == 7:
        reverse = 1
        break
    else :
        reverse+=str(n)

    temp //= 10



if(isPrime(number) and isPrime(reverse)):
    print('yes')
else:
    print('no')