본문 바로가기

study/알고리즘

[알고리즘/프로그래머스] 소수 찾기

연습문제 > 소수 찾기

 

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

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

programmers.co.kr

 


처음에 시간 초과가 나서 참고한 프로그래머스 질문하기 글 🔽

효율성 테스트를 위한 조그마한 조언 | 프로그래머스 (programmers.co.kr)

1. 1보다 큰 모든 자연수는 소수의 곱으로 이루어져 있다.
2. 어떤 자연수 n이 있을 때, √n 보다 작은 모든 소수들로 나누어 떨어지지 않으면 n은 소수입니다.
3. 2보다 큰 모든 짝수는 어차피 합성수입니다. 어차피 2로 나누어 떨어지기 때문

나의 풀이

- end를 if문 안에서 계산하게 되면 시간 초과

prime_list = []

def is_prime(n):
    end = int(pow(n, 1/2))+1
    for i in prime_list:
        if n%i == 0:
            return 0
        if  i > end:
            break
    prime_list.append(n)
    return 1

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


다른 사람의 풀이

- 에라토스테네스의 체
: 그리스의 수학자이자 지리학자인 에라토스테네스가 고안한 소수(素數)를 찾는 방법으로, 이 방법으로 소수를 찾으려면, 2부터 시작해 자연수를 차례로 쓴 다음, 2 이외의 2의 배수, 3 이외의 3의 배수, 5 이외의 5의 배수의 순서로 수를 지워나가 끝에 남는 수가 소수이다.

[네이버 지식백과] 에라토스테네스의 체 [Eratosthenes' sieve] (두산백과)


- 아래의 방법이 에라토스테네스의 체를 set 함수를 활용하여 푼 방식

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)