루나의 TIL 기술 블로그

프로그래머스 level 1 소수 찾기

06 Jul 2021 | 기초 프로그래머스 TIL

걸린 시간 : 3시간

문제 설명

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

입출력 예

n result
10 4
5 3

사고과정

2부터 해당 숫자까지 나누어보고 나누어지지 않으면 소수로 판단한다.

제출답안

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

def solution(num):
    ans = []
    for i in range(2, num+1):
        if isPrime(i):
            ans.append(i)
    return len(ans)

시간초과로 정확성테스트 10,11,12번와 효율성 테스트를 전부 실패했다.

소수 판별하는 부분을 제곱근 이용하는 방법으로 바꿨는데 런타임에러로 실패한다.

def isPrime(n): 
    if n == 1 :
        return False
    for div in range(2,int(math.sqrt(n))+1):
        if n%div == 0:
            return False
    return True

질문하기에 보니까 에라스토테네스의 체를 써야 통과할 수 있다고한다.

def solution(n):
	# 2부터 n까지의 숫자 배열 만들기
    num_set = set(range(2, n+1))

    for i in range(2, n+1): # 2~n까지의 수 i 에 대해
        if i in num_set: #i 가 num 안에 있으면
            num_set -= set(range(i*2, n+1, i))
             #i의 배수set(i의 2배수 부터 n까지수 중 i 만큼 간격있는 수들)를 num에서 빼주기
    answer = len(num_set)
    return answer

주요 포인트 및 생각해볼 점

어제 소수 리스트 만들기를 했으면서 오늘 더 간단한 소수 찾기를 하는데도 오래걸렸다.
어제 에라스토테네스의 체를 익혀서 내것으로 만들지 않은 까닭이다.
하지만 어제는 소수를 찾는 것만으로도 공부가 되었다고 생각했다.

Related Posts