[프로그래머스 파이썬] 소수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/12921

제곱근까지 소수 판별 완전탐색

import math

def is_prime(n):
    for i in range(2, int(math.sqrt(n)) + 1): # 제곱근까지 소수 판별
        if n % i == 0:
            return False

    return True

def solution(n):
    answer = 0

    for i in range(2, n + 1):
        if is_prime(i) == True:
            answer += 1

    return answer

에라토스테네스의 체

1. 배열 생성 후 값 초기화
2. 2부터 시작, 특정 숫자의 배수에 해당하는 숫자를 제거 (특정 숫자는 냅둬야한다.) (지워진 수는 건드리지 않는다.)
3. 2부터 마지막까지 True인 것의 개수를 출력한다.

• 시간복잡도 O(n log log n)
• 알고리즘 수행 시 n만큼의 리스트를 할당해야해서 메모리가 n만큼 소비된다.

def solution(n):
    answer = 0
    # 1
    array = [True for i in range(n + 1)]
    
    # 약수의 성질에 따라 가운데 약수(제곱근)까지만 확인
    for i in range(2, int(n ** (1/2)) + 1):
        if array[i] == True: # i가 소수인 경우
        	# 2 (i를 제외한 모든 숫자 false)
            j = 2
            while i * j <= n:
            	
                array[i * j] = False
                j += 1
                
    # 3
    return array.count(True) - 2