[Python][백준] 1149. 소수&팰린드롬 / 브루트포스, 에라토스테네스의 체 (S1)

🔗링크 :  

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

---

🗒️파이썬 코드 풀이

N = int(input())
lst = [0] * 2000000
lst[0],lst[1] = 1,1
count = 2 

while count < 2000000 :
    if lst[count] == 0:
        i = 2
        while count*i < 2000000:
            lst[count*i] = 1
            i+=1 
    count += 1

while True:
    if lst[N] == 0 and  str(N) == str(N)[::-1]:
        print(N)
        break
    else:
        N += 1

 

1. 문제 내용은 깔끔하다. 

- 최소한의 시간 복잡도로 소수를 만들 수 있는지?

- 팰린드롬을 구현 할 수 있는지 ?

 

2. 먼저 소수 리스트부터 만들어보자. 

1. 넉넉하게 2,000,000 크기의 리스트를 만들어 준다.

2. 예외 값인 0과 1의 값은 미리 채워준다.  (꼭 채워줘야함)

3. count를 1씩 증가 시키며, 
lst에서 count만큼의 인덱스 값이 0이면 해당 배수 1로 처리
(count 값이 커질 수록 연산 기하급수적으로 감소)

 

3. 다음으로 팰린드롬은 간단하게 [: : -1] 인덱싱이면 끝이난다. 

 

4. 이후 lst[N] 값이 0, 즉 소수인 것과 팰린드롬인 값을 찾으면 된다.

 

 

📌  문제 코멘트

팰린드롬은 간단하고, 에라토스테네스의 체가 좀 헷갈렸다.

단순 무식하게 반복문하면 안되고 배수를 처리하는 방식을 기억하자.

---

📚문제

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

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

입력

첫째 줄에 N이 주어진다.

출력

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

예제 입력 1 복사

31

예제 출력 1 복사

101