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

연습문제 > 소수 찾기

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

 

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

효율성 테스트를 위한 조그마한 조언 | 프로그래머스 (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)