소수를 구하는 모든 방법

소수 (prime numberr)

• 약수가 1, 자기자신 밖에 없는 정부 (1은 소수 아님)

1> is_prime_01

8.255400000000204e-05초 걸렸음!

def is_prime_01(num):
    for i in range(2, num):
        if num % i == 0:
            return False
    return True

2> is_prime_02

3.030700000000025e-05초 걸렸음!

def is_prime_02(num):
    i = 2
    while i*i <= num:
        if num % i == 0:
            return False
        i += 1
    return True

3> 에라토스테네스의 체(Sieve of Eratosthenes) 이용

def solution(num):
    nums = set(range(2, num+1))
    for i in range(2, num+1):
        if i in nums:
            nums -= set(range(i*i, num+1, i))
    return len(nums)

4> 짝수를 건너뛰기

5> 제곱근가지만 배수를 지우기

Reference

• https://burningrizen.tistory.com/31?category=801405
• https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4