Lv1. 소수 찾기

코딩테스트 연습 > 소수 찾기

1. 풀이 설명

2부터 n까지 for 문을 돌면서 소수인지를 검사한다.
소수인지를 검사할 때는 2부터 해당 숫자의 제곱근까지만 for 문을 돌면서 나누어떨어지는지 확인하면 된다.

2. 나의 풀이

def solution(n):
    answer = 0
    for i in range(2, n+1):
        if is_prime(i):
            answer += 1
    return answer

def is_prime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

3. 나의 풀이 2

• 소수를 판단하는 함수를 만들고, 2부터 n까지 소수인 경우(True, 1)의 합을 반환한다.

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

3. 배운점

1. 소수 검사를 할 때는 제곱급까지만 검사하면 된다.
   is_prime(n)함수 에서 for i in range(2, int(n ** 0.5) + 1): 대신 for i in range(2, n):을 사용하면 시간초과가 된다.

2. 제곱근까지만 검사하면 되는 원리는 아래와 같다.

24의 경우
1 * 24
2 * 12
3 * 8
4 * 6 		<----- int( 24 ** 0.5 ) = 4
...

25의 경우
1 * 25
5 * 5		<------ 25 ** 0.5 = 5
...

3. python 에서 True 는 1 이므로, 리스트 내의 True 들의 합으로 count 를 구할 수 있다.

sum([True, True, False, True]) # 3