1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.(1은 소수가 아닙니다.)
🔗제한 사항
- n은 2이상 1000000이하의 자연수입니다.
🔗입출력예
입출력 예 #1 1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환
입출력 예 #2 1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환
👉 문제풀이
숫자가 소수인지를 판별하기 위해 is_prime 변수를 사용하였다.
소수인 경우 answer을 증가시킨다.
소수를 판별하는 과정에서 제곱근을 활용하는 이유는 효율성과 정확성을 동시에 고려하기 위해서입니다. 일반적으로 주어진 숫자 n이 소수인지 판별하기 위해서는 2부터 n-1까지의 모든 숫자로 나누어 보아야 합니다. 그러나 이렇게 모든 숫자를 나누어 보는 것은 비효율적입니다.
제곱근을 활용하는 이유는 다음과 같습니다. 어떤 수 n이 소수가 아니라면, 그 수는 반드시 두 개의 작은 인수를 가지고 있을 것입니다. 그렇다면 그 두 개의 작은 인수 중 적어도 하나는 n의 제곱근보다 작거나 같을 것입니다. 예를 들어, n이 100이라면 10 * 10 = 100이므로 인수 중 하나는 10 이하입니다. 따라서, 소수를 판별할 때는 2부터 n의 제곱근까지만 확인해도 충분합니다. 만약 2부터 n의 제곱근까지의 숫자로 나누어서 나누어떨어지는 경우가 하나라도 있다면 n은 소수가 아닙니다. 그렇지 않다면 n은 소수입니다. 이렇게 제곱근까지만 확인하는 것은 효율성을 높일 수 있습니다. 왜냐하면 n의 제곱근보다 큰 수로 나누어봤자 이미 앞서서 확인한 작은 수로도 나누어떨어지지 않았기 때문입니다. 따라서 불필요한 계산을 줄여 효율적인 소수 판별이 가능합니다.
def solution(n):
# 0과 1은 소수가 아니므로 초기값을 2로 설정
answer = 0
# 주어진 범위 내의 숫자에 대해 소수 여부를 판별
for num in range(2, n+1):
is_prime = True
# 2부터 현재 숫자의 제곱근까지 나누어 소수 여부 확인
for i in range(2, int(num ** 0.5) + 1):
if num % i == 0:
is_prime = False
break
# 소수인 경우 answer 증가
if is_prime:
answer += 1
return answer
👉 다른사람 문제풀이
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)
👉 다른사람 문제풀이(에라토스테네스의 체)
숫자의 제곱근까지만 확인: 주어진 숫자 num이 소수인지 판별할 때, num의 제곱근까지만 확인해도 충분합니다. 따라서 range(2, int(num ** 0.5) + 1)로 범위를 제한하여 반복문을 수행하면 더 효율적입니다.
홀수만 확인: 2를 제외한 모든 소수는 홀수입니다. 따라서 짝수인 숫자는 소수가 아니므로, 짝수인 경우에는 소수 여부를 확인하지 않고 건너뛰면 됩니다.
에라토스테네스의 체: 주어진 범위 내의 모든 숫자를 한 번에 판별하는 방법으로, 소수 여부를 기록하는 리스트를 사용합니다. 초기에 모든 숫자를 소수로 표시한 후, 소수가 아닌 숫자들을 걸러내는 방식입니다. 이를 활용하여 범위 내의 소수를 빠르게 구할 수 있습니다.
def solution(n):
if n < 2:
return 0
# 주어진 범위 내의 숫자에 대해 소수 여부를 판별하는 리스트
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
# 2부터 숫자의 제곱근까지 소수 여부를 판별
for num in range(2, int(n ** 0.5) + 1):
if is_prime[num]:
# num의 배수들은 소수가 아님
for i in range(num * num, n + 1, num):
is_prime[i] = False
return sum(is_prime)
