[알고리즘][Python] 백준(BOJ) 1747 소수&팰린드롬_파이썬

 

1747 소수&팰린드롬    https://www.acmicpc.net/problem/1747

1747번: 소수&팰린드롬

 

 

 

 

 

 

 

문제 풀기 전 공부할 것 : 소수 구하는 방법, 에라토스테네스, 팰린드롬

 

 

 

 

 

 

 

풀이 1

<내용>

• 에라토스테네스의 체를 이용해서 1,000,000 이하의 범위에서 소수를 찾는다.

• 그리고 n보다 크거나 같으면서 1,000,000보다 작거나 같은 수에서 팰린드롬인 수를 먼저 찾아준다.

• 팰린드롬인 수면 소수인지 위에서 구한 prime을 통해 확인한다.

• 만약 n보다 크거나 같으면서 1,000,000 이하의 범위에서 소수가 나오지 않는다면 1,000,000보다 크면서 가장 작은 소수이면서 팰린드롬인 수 1003001이 출력되도록 한다.

 

• 주의할 부분 : n의 범위는 나와있다고 해서 그 범위 내에서 결괏값이 나와야 하는 건 아니다.

  • n이 특정수를 넘어가면 1,000,000내에서 소수이면서 팰린드롬인 수가 나오지 않는다. 그럴 때는 1,000,000를 넘어가지만 가장 작은 소수이면서 팰린드롬인 수 1003001가 출력되도록 해야 한다.

 

 

<코드>

n = int(input())
M = 1000001
prime = [False, False] + [True] * (M-2)
for i in range(2, int(M**0.5)+1):
    if prime[i]:
        for j in range(i+i, M, i):
            if prime[j]:
                prime[j] = False

res = 0
for i in range(n, M):
    if i == 1:
        continue
    if str(i) == str(i)[::-1]:
        if prime[i]:
            res = i
            break
if res == 0:
    res = 1003001
print(res)

 

 

+) 에라토스테네스의 체를 이용하지 않고 소수임을 찾아보자. (에라토스테네스의 체로 prime에 모든 소수에 대한 정보를 넣으면 메모리도 많이 차지하고 시간도 더 오래 걸린다.)

 

 

 

 

 

 

 

 

풀이 2

<내용>

• 위의 흐름과 동일하다.
• 에라토스테네스의 체를 이용하지 않고 소수를 찾는 for문을 만든다.

 

 

<코드>

n = int(input())
M = 1000001
res = 0
for i in range(n, M):
    if i == 1:
        continue
    if i == 2:
        res = i
        break
    if str(i) == str(i)[::-1]:
        if i % 2 == 0:
            continue
        flag = True
        for j in range(2, int(i**0.5)+1):
            if i % j == 0:
                flag = False
                break
        if flag:
            res = i
            break
if res == 0:
    res = 1003001
print(res)

 

 

 

 

 

 

 

 

 

시도 1 ==> 범위 내에서 조건을 만족하는 수가 없는 경우 출력이 이뤄지지 않는다.

 

<내용>

• n <= x <= 1,000,000에서 소수이면서 팰린드롬인 수가 없으면 출력이 없다.
• 그러나 출력의 수에 대한 조건이 있는 것이 아니므로 1,000,000보다 크지만 가장 작은 소수이면서 팰린드롬인 수 1003001을 출력해야 한다.

 

• 예 - 324423을 입력하면 출력값이 없다.

 

 

<코드>

n = int(input())
M = 1000001
for i in range(n, M):
    if i == 1:
        continue
    if i == 2:
        print(i)
        break
    if str(i) == str(i)[::-1]:
        if i % 2 == 0:
            continue
        flag = True
        for j in range(2, int(i**0.5)+1):
            if i % j == 0:
                flag = False
                break
        if flag:
            print(i)
            break