[12921] 소수 찾기 python3

문제 설명

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를 반환

문제 풀이 

1. n의 숫자를 소수 판별문을 통해 소수인지 확인하고 소수가 맞다면 answer 변수에 +1 를 해준다.

import math
def sosu(x):
    if x == 2 : 
        return True
    elif x== 1 : 
        return False
    for i in range(2,int(math.sqrt(x) +1)):
        if x%i == 0:
            return False
    return True
def solution(n):
    answer = 0
    for i in range(1,n+1):
        if sosu(i) == True:
            answer+=1
    return answer

이 문제는 배열이 클 경우 효율성에서 문제가 생길 수 있습니다. 따라서 소수판별 할 때 먼저 제곱근을 해주게 되면 시간을 단축할 수 있습니다. 

예를 들어 100000 이라는 숫자를 소수 판별할 경우 2부터 100000번까지 반복하면 시간이 오래걸리니 먼저 제곱근을 통해 100으로 만든 후 100까지 반복해서 소수가 맞는지 판별하면 더욱 빠르게 판별할 수 있습니다.

다른 사람 문제 풀이

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)

1. 2부터 n까지 num에 저장한다.2. i일때마다 해당하는 값에 배수를 제거한다.

3. 남은 값은 소수만 있으므로 길이를 리턴한다.

생각 정리

저는 단순히 소수인지 판별해서 문제를 풀었지만 에라토스테네스의 체 공식을 이용해서 풀면 훨씬 시간도 줄일 수 있고 이해하는데 더 좋은거 같습니다.