본문 바로가기
Engineering WIKI/Programmers

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

by wonos 2022. 4. 19.
 

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

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 제한 조건 n은 2이상

programmers.co.kr

내 풀이 (실패)

  • 테스트 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)