[프로그래머스]/python

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

0_TLS 2024. 3. 2. 18:14

문제 보기

더보기

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건

  • n은 2이상 1000000이하의 자연수입니다.

입출력 예

n                                                                                                         result
10 4
5 3

입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

<나의 풀이> - 시간 초과

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

 

*에라토스테네스의 체 알고리즘 이용

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

 

2부터 n까지의 숫자중에서 에라토스테네스의 체로 소수를 찾으려면, 2부터 시작해 n까지의 자연수를 차례로 쓴다. (2, 3, 4, ..., n)
그리고 2 이외의 2의 배수를 지운다(p=2). 이때 2가 최초의 소수가 된다.
그 다음 소수인 3을 제외한 3의 배수를 지운다(p=3).
이 방법을 다음에 지울 소수, 즉 p의 제곱이 n 보다 커질 때까지, 이 방법을 계속한다(p2≥n).

 

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

 

<정답>

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)