[프로그래머스/파이썬] 소수 찾기

문제 설명

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

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

---

제한 조건

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

---

입출력 예

n	result
10	4
5	3

---

내 풀이

for j range(2, i) 까지 돌렸을 때는 시간 초과가 뜹니다.

주어진 수 이하의 소수를 구하고자 할 때, 제곱근 까지만 소수 판별을 해도 소수 판별이 가능합니다.

에라토스테너스의 체를 사용하면 더 빠르게 구현할 수 있더라구요...

나중에 구현해봐야겠습니다.

import math
def solution(n):
    cnt = 0
    for i in range(2,n+1):
        isPrime = True
        for j in range(2,int(math.sqrt(i))+1):
            if i % j == 0:
                isPrime = False
                break
        if isPrime:
            cnt+=1
    
    return cnt

 

---

다른 사람 풀이

에라토스테너스의 체를 파이썬스럽게 구현한 것 같습니다.

n = 10 일 때

num = (2,3,4,5,6,7,8,9,10)

i는 2부터 10까지 돌고 i 가 num 안에 있다면 if 문 내부를 수행합니다.

num-=set(range(2*i,n+1,i)) 은 num = num - set(range(2*i,n+1,i)) 입니다.

이때, range 세 개의 인자는 range(start,stop,step)를 나타냅니다.

따라서 i = 2 일 때, set(range(2*i,n+1,i)) 는 (4,8) 가 됩니다.

num에서 이를 빼면 num = (2,3,5,6,7,9,10) 이 됩니다.

이를 반복 하면 num에 남는 것은 (2,3,5,7)이 됩니다.

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)

 

[파이썬/파이썬 공부] - [파이썬] 소수 판별 '에라토스테네스의 체'

[파이썬] 소수 판별 '에라토스테네스의 체'