π§© Algorithm/ꡬν
μλΌν μ€ν λ€μ€μ 체
HelloRabbit
2023. 2. 13. 20:34
728x90
Goal
1. μμ μ μνκΈ°
2. μμ μ°Ύλ μκ³ λ¦¬μ¦ - "μλΌν μ€ν λ€μ€μ 체" μ΄ν΄νκΈ°
μμλ?
μμλ μ«μ μ€ λ μμ κ³Ό 1λ‘λ§ λλ μ§λ μλ€. μ¦, κ·Έ 2κ°μ μ μ΄μΈμ λ€λ₯Έ μλ‘ λλ μ§λ€λ©΄ μμκ° μλ "ν©μ±μ" λΌκ³ λ§ν μ μλ€!
μμ)
μμ : 2, 3, 5, 7, 11, 13, 17, 19, ...
κ·Έ μΈ : 4 (2λ‘ λλ μ§λκΉ), 6 (2μ 3μΌλ‘ λλ μ§λκΉ), 8 (2λ‘ λλ μ§λκΉ), 9 (3μΌλ‘ λλ μ§λκΉ), ...
"μλΌν μ€ν λ€μ€μ 체"λ μΈμ νμνκ°?
- Nμ΄λΌλ μ«μκ° μμμΈμ§ μλμ§ νλ¨νκΈ° μν΄μλ 2λΆν° N/2 κΉμ§μ μ«μλ‘ λλ λ΄μΌ μ μ μλ€
- νμ§λ§ 2λΆν° 100κΉμ§μ μ«μ μ€μμ μμλ₯Ό μΆλ ₯νλΌκ³ νλ€λ©΄ μ΄μ€ forλ¬Έμ λλ €μΌνκ³ μκ° λ³΅μ‘λλ O(n^2)μΌλ‘ λ리λ€
# μμ μ°Ύλ ν¨μ
def get_prime(start, end):
prime_numbers = []
for target_num in range(start, end):
prime_numbers.append(target_num)
for k in range(2, target_num//2):
if target_num % k == 0:
prime_numbers.pop() # μ«μ target_numκ° kλ‘ λλ μ§λ€λ©΄ μμκ° μλλ―λ‘ μ κ±°
break
return prime_numbers
# 2μμ 100κΉμ§μ μ«μ μ€ μμ μ°ΎκΈ°
print(get_prime(2, 101))
- κ·Έλμ μλΌν μ€ν λ€μ€μ 체λ₯Ό νμ©νλ©΄ μ’λ€!!
"μλΌν μ€ν λ€μ€μ 체"λ?
- μμλ₯Ό λ°κ²¬ νμ λ κ·Έ μμμ λ°°μλ₯Ό λͺ¨λ μ μΈμν¨λ€

- μ κ·Έλ¦Όμμ 2κ° μμλΌλκ±Έ λ°κ²¬νκ³ λλ¨Έμ§ 2μ λ°°μλ€μ 2λ‘ λλ μ§κΈ° λλ¬Έμ μμκ° μλ κ²μ μ μ μμ΄ μ μΈμν¨λ€
- κ·Έ λ€μ 3μ΄ μμλΌλκ±Έ λ°κ²¬νκ³ λλ¨Έμ§ 3μ λ°°μλ€μ 3μΌλ‘ λλ μ§κΈ° λλ¬Έμ μμκ° μλλ―λ‘ μ μΈμν¨λ€
- κ·Έ λ€μ 5κ° μμλΌλκ±Έ λ°κ²¬νκ³ 5μ λ°°μλ₯Ό μ μΈμν¨λ€
- κ·Έ λ€μ 7μ΄ μμ...
- κ³μ λ°λ³΅...