[파이썬 Python] 에라토스테네스의 체(소수 구하기) 개념과 예제 - (백준 1747)

에라토스테네스의 체 알고리즘

에라토스테네스의 체는 소수를 찾는 방법 중 하나입니다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열합니다.
2. 2 자신을 제외한 2의 배수를 모두 지웁니다.
3. 남아있는 수 가운데 3은 소수이므로 놔두고, 자신을 제외한 3의 배수를 모두 지웁니다.
4. 남아있는 수 가운데 5는 소수이므로 자기 자신을 제외한 5의 배수를 모두 지웁니다.
5. 남아있는 수 가운데 7은 소수이므로 자신을 제외한 7의 배수를 모두 지운다.
6. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남게됩니다.

---

Python 3으로 구현

일단 A 리스트를 인덱스와 수가 같도록 [0,0,2,3,4,5,6,7,8,9 ...] 로 초기화 해줍니다. (0,1은 제외)

2부터 2의 배수들을 차례로 0으로 만들어 줍니다.

이 방식을 반복하면, 값이 0을 제외한 값들은 소수밖에 안남게 됩니다.

# 소수 구하기
# 에라토스테네스의 체
import math
m, n = map(int,input().split())
A = [0]*(n+1)
# initialize
for i in range(2,n+1):
    A[i] = i

for i in range(2,int(math.sqrt(n))+1):
    if A[i] == 0:
        continue
    for j in range(i+i , n+1, i):
        A[j] = 0

for i in range(2 , n+1):
    if A[i]!=0:
        print(i)

---

예제 - 백준 1747

소수&팰린드롬

어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.

어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.

 

출력

첫째 줄에 조건을 만족하는 수를 출력한다.

예제 입력

31

예제 출력

101

---

파이썬 코드 풀이

문제 뜻대로 에라토스테네스의 체 알고리즘으로 1,000,000까지의 소수들만 구하고, 그 소수들이 좌우가 같은지 함수로 판별한후 출력하도록 하겠습니다.

그러나 입력 값이 최대 1,000,000 이기 때문에, 만약에 n 이 1,000,000로 주어지면, 그 보다 큰 수들을 구해야되는데 1,000,000이 끝이므로 검사하는 범위를 늘리는 등의 조치를 취해야한다는 것입니다.

 

그래서 num = [0] * 10000001 로  배열의 크기를 10배 늘려서 테스트 코드를 실행해 봤습니다.

n에다가 1000000을 입력해 보니 1003001이 나왔습니다. 즉, 1000000내에 적합한 소수&팰린드롬 수가 없다면 바로 다음수가 1003001 이므로 이 수를 출력하면 된다는 것입니다.

그래서 기존 범위내에 적합한 수가 없어서 result가 0이 나오면 1003001을 출력하도록 작성했습니다.

 

#에라토스테네스의 체
n = int(input())
num = [0]*(1000001)
for i in range(2,1000001):
    num[i] = i

def isPelindrome(t):
    n_string = str(t)
    length = len(n_string)
    for i in range(int(length/2)+1):
        if n_string[i] != n_string[length-1-i]:
            return False
    return True

for i in range(2,1000001):
    if num[i] == 0:
        continue
    for j in range(i+i ,1000001,i):
        num[j] = 0

result = 0
for i in range(n, 1000001):
    if num[i]!=0 and isPelindrome(i):
        result = i
        break
if result == 0:
    result = 1003001
print(result)