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

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.(1은 소수가 아닙니다.)

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

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

: It got answers but the efficiency doesn't look good

→ Sieve of Eratosthenes

def solution(n):
    answer = 0
    
    nums = list(range(2, n + 1))
    i = 2

    finish = int(len(nums) ** 0.5) + 1
    while i < finish:
        j = i
        while j < len(nums):
            if nums[j] % i == 0:
                nums[j] = False

            j += 1
        i += 1

    for a in nums:
        if a != False:
            answer += 1

    return answer

: Less time but still cannot pass