[프로그래머스] 소수 찾기 (2) - Python

programmers.co.kr/learn/courses/30/lessons/12921

코딩테스트 연습 - 소수 찾기

import math

def solution(n):
    answer = 0
    arr = [1] * (n+1)
    for i in range(2, int(math.sqrt(n))+1):
        if arr[i]:
            for j in range(2*i, n+1, i):
                arr[j] = 0
    for i in range(2, n+1):
        if arr[i]:
            answer += 1
    return answer

소수 찾는 방법

: 에라토스테네스의 체 이용하기!

1. 2부터 구하는 수까지 모든 수를 나열 -> 제곱근 이용해서 시간 줄일 수 있음

2. 2부터 자기 자신을 제외한 2의 배수, 3의 배수, 5의 배수, 7의 배수 순서대로 지우기

3. 지워지지 않은 수들이 소수!!