[프로그래머스 코딩테스트 연습 > 정렬] 소수 찾기 (Python3) Lv1

이 문제의 목표는 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 구하는 것이다.

소수는 1과 자기 자신으로만 나누어지는 수를 의미한다.

코드

import math

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

def solution(n):
    return sum([isPrime(n) for n in range(2, n + 1)])

 

문제 해설

1. isPrime(n) 함수: 주어진 숫자 n이 소수인지 판별하는 함수이다.
   • 입력: 정수 n
   • 출력: True 또는 False
   • 작동 원리:
     • 입력된 숫자 n의 제곱근까지의 수를 검사한다.
     • 제곱근까지만 검사하는 이유는, 소수가 아닌 수는 작은 소인수를 갖기 때문이다. 예를 들어, 16은 4*4로 나누어지므로, 제곱근인 4까지만 검사하면 된다.
     • n이 2부터 int(math.sqrt(n)) + 1까지의 어떤 수로도 나누어 떨어지지 않으면 소수로 간주한다.
     • 하나라도 나누어 떨어지는 수가 있다면 소수가 아니므로 False를 반환하고, 그렇지 않으면 True를 반환한다.
2. solution(n) 함수: 주어진 숫자 n까지의 모든 소수를 찾아 그 개수를 반환하는 함수이다.
   • 입력: 정수 n
   • 출력: 1부터 n까지의 소수 개수
   • 작동 원리:
     • 2부터 n까지의 모든 수에 대해 isPrime() 함수를 호출하여 소수인지 확인한다.
     • isPrime() 함수가 True를 반환하면, 그 숫자는 소수이다.
     • 리스트 내포를 사용하여 소수 개수를 세고, sum() 함수를 사용하여 최종 결과를 반환한다.