π‘ 쑰건
- μλΈνμ€ν¬κ° μ‘΄μ¬νλ€.
- 2 μ΄μμ μμ°μ Nμ΄ 1κ³Ό Nμ μ μΈνκ³ μ΄λ€ μμ°μλ‘λ λλμ΄ λ¨μ΄μ§μ§ μμ λ μμλΌκ³ νλ€.
- μμ°μ Kκ° μ£Όμ΄μ§λ€.(1 ≤ K ≤ 500,000)
- kλ²μ§Έ μμλ₯Ό ꡬνλ λ¬Έμ
- μν, μλΌν μ€ν
λ€μ€μ 체 μ νμ λ¬Έμ
π₯ μμ€ μ½λ
BIG_NUM = 10**7
k = int(input())
array = [1 for _ in range(BIG_NUM + 1)]
answer = []
for i in range(2, BIG_NUM + 1):
if array[i]:
answer.append(i)
for j in range(i+i, BIG_NUM + 1, i):
array[j] = 0
print(answer[k - 1])
π μμ λ° μ€νκ²°κ³Ό
μμ
3
μ€νκ²°κ³Ό
5
β¨οΈ λ¬Έμ νμ΄
- μλΌν μ€ν
λ€μ€μ 체λ₯Ό μ¬μ©νμ¬ νμ΄λ₯Ό νλ©΄ λ©λλ€.
- i κ° μμμΌ λ, iμ λ°°μλ μμκ° μλλ€ λΌλ μμ΄λμ΄μμ μμμ ν©λλ€.
- iκ° μμλ‘ νλ³μ΄ λμλ€λ©΄, 10^7 κΉμ§ κ²μ¬λ₯Ό νλ©΄μ iμ λ°°μλ λͺ¨λ array λ°°μ΄μμ 0μΌλ‘ 체ν¬ν©λλ€.
- μμλ‘ νλ³λ iλ answerμ μΆκ°ν΄μ€λλ€.
πΎ λλμ
- μλΌν μ€ν
λ€μ€μ μ²΄κ° μ΅μνμ§ μμ μνμμ νμμλ λ¬Έμ μλ€.
- μ§κΈμ λ¬Έμ λ₯Ό μ₯ μ½μΌλ λ°λ‘ νμ΄κ° μκ°μ΄ λ¬λ€.