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

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

내 풀이 (실패)

• 테스트 10 ~ 테스트 12 : 실패
• 효율성 : 실패

def is_prime_number(x):
    for i in range(2, x):
        if x % i == 0:
            return False
    return True

def solution(n):
    answer = 0
    for i in range(2, n + 1):
        if is_prime_number(i) == True:
            answer += 1
    return answer

 

다른 방법

• 소수를 구하기 위해 2부터 비교하는 숫자까지 나눠가면서 나머지를 확인하는 방법이 있지만 효율성 부분에서 시간이 상당히 걸리게 됩니다.
• 여기서 에라토스테네스의 체 방법을 이용합니다. 소수인지 판별하고 싶은 수의 제곱근 까지의 배수를 제외시켜주는 방법입니다. 즉, 10을 판별하고 싶으면 10의 제곱근은 3.xxx이므로 [2 : 10] 에서 2, 3의 배수를 제외시켜주면 됩니다.

def solution(n):
    num = set(range(2, n + 1))

    for i in range(2, n + 1):
        if i in num:
            num -= set(range(2 * i, n + 1, i))
    return len(num)