프로그래머스 - 소수 찾기 (Python)

문제

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

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

 

풀이

def solution(n):
    answer = 0
    
    # 1. 1은 소수가 아니므로 2부터 n까지의 수를 확인한다.
    for x in range(2, n+1):
    
    	# 2. x가 2부터 x의 제곱근 사이의 자연수로 나누어 떨어지면, 소수가 아니다.
        for j in range(2, int(x ** 0.5) + 1):
            if x % j == 0:
                isPrime = False
                break
                
        # 3. x가 2부터 x의 제곱근 사이의 자연수로 나누어 떨어지지 않는다면, 소수이다.
        if isPrime == True:
            answer += 1
            
    return answer

 

이 문제는 효율성을 고려해야 한다.

효율성을 고려하지 않고 간단하게 생각하면, 아래와 같이 x가 2부터 x-1 사이의 자연수로 떨어지는 경우를 확인할 수 있다.

하지만 이는 시간복잡도가 O(n)로, x가 증가할수록 연산 횟수도 비례하여 증가한다. (만약 n이 1000000 이라면..?)

for j in range(2, x):
    if x % j == 0:
        isPrime = False
        break

 

이를 해결하기 위해서는 x가 2부터 x의 제곱근 사이의 자연수로 떨어지는지만 확인하면 된다.

 

16의 약수는 1, 2, 4, 8, 16 이고, 제곱근 4 이상의 약수 8, 16이 있다는 뜻은.. 그 짝이되는 2, 4가 반드시 존재한다는 뜻이다.

따라서 x가 2부터 x의 제곱근 사이의 자연수로 나누어 떨어진다면! x는 소수가 아니다.

나누어 떨어지지 않는 수의 갯수를 answer로 return 해주면 끝!