[230228] 소수 구하기(에라토스테네스의 체) - Python

• 원래 구하던 소수 구하기
  • 나누어 떨어지면 약수가 존재하므로 소수X
  • 시간이 오래 걸려 효율성에서 실패할 확률 높음

def isprime(n):
	for i in range(2,int(n**0.5)+1):
        if n%i == 0:
        	return False
    else:
    	return True

 

• 에라토스테네스의 체
  • 가장 먼저 소수를 판별할 범위만큼 배열을 할당 후 이후에 하나씩 지워나가는 방법
    • ex) 2의 배수 지우기, 3의 배수 지우기, 5의 배수 지우기....
  • O(n**0.5)

def solution(n):
    arr = [i for i in range(n+1)]
    for i in range(2,int(n**0.5)+1):
        if arr[i]:
            j = 2
            # i의 배수 지우기
            while i*j <= n:
                arr[i*j] = 0
                j += 1
    
    answer = []
    for a in arr[2:]:
        if a:
            answer.append(a)
    return answer