에라토스테네스의 체

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

문제 설명 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 제한 조건 n은 2이상 1000000이하의 자연수입니다. 입출력 예 n result 10 4 5 3 내 풀이 for j range(2, i) 까지 돌렸을 때는 시간 초과가 뜹니다. 주어진 수 이하의 소수를 구하고자 할 때, 제곱근 까지만 소수 판별을 해도 소수 판별이 가능합니다. 에라토스테너스의 체를 사용하면 더 빠르게 구현할 수 있더라구요... 나중에 구현해봐야겠습니다. import math def solution(n): cnt = 0 for i in range(2,n+1): isPrime = True for..

[파이썬] 소수 판별 '에라토스테네스의 체'

에라토스테네스의 체 1. 소수를 구하고자 하는 범위를 2부터 나열 2~n 사이의 소수를 구하고자 할 때 다음과 같이 나열합니다. 0과 1은 False로 두고, 2~n-1개까지 True로 둡니다. a = [False,False] + [True]*(n-1) 2. 2부터 나열한 수까지 반복하며 배수 지우기 2부터 n+1까지 반복문을 돌리고 a의 i 번째 인덱스가 True 이면 primes 리스트에 추가합니다. 만약 n=10, i= 2이면, 현재 a[2]는 True이므로 primes에 2를 추가하고 2의 배수인 4,8이 False가 됩니다. 3도 primes에 추가되고 배수인 6,9가 False가 됩니다. 4는 2의 배수를 지우는 단계에서 False가 되었으므로 if문을 통과하지 못합니다. 5는 True 이므로..