소수 찾기 (Level 1)

1. 문제

2. 나의 풀이

2-1. 첫번째 시도

def solution(n):
    answer = 0
    is_prime = True
    
    for i in range(2, n+1):
        is_prime = True
        for j in range(2, i):
            if i % j == 0:
                is_prime = False
                break
        if is_prime: answer += 1
    return answer

• 시간 초과!!!!

2-2. 두번째 시도

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

def solution(n):
    count = 0
    for i in range(2, n+1):
        if is_prime(i):
            count += 1
    return count

2-3. 세번째 시도

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)

3. 남의 풀이

• https://burningrizen.tistory.com/86

4. 느낀 점

• 유명한 수학자가 이미 증명한 방법이 있음. 에라토스의 체 참조