[백준] 1978번. 소수 찾기

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

 

 

 

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

 

 

 

 

출력

주어진 수들 중 소수의 개수를 출력한다.

 

 

예제입력

해설 코드

n = int(input())

num_list = list(map(int, input().split()))

count  = 0

def is_prime(num):
    if num == 1: # 1은 소수가 아니다
        return False 
    i = 2
    while i < num:
        if num % i == 0:
            return False
        i += 1
    
    return True

for num in num_list:
    if is_prime(num): # true인 경우에 count가 시행됨
        count += 1
        
print(count)

소수란?

소수는 영어로 Prime Number 로서,

1과 자기자신 외에는 어떠한 수로도 나누어 떨어지지 않는 수이다.

 

 

소수를 찾는 알고리즘

특정 수 n이 소수인지 아닌지 판별하는 방법은 바로 위 '소수의 특징'을 활용하여 2부터 n-1 까지의 수로 해당 수를 나눠보고, 이 과정에서 어떠한 수에 의해 나누어 떨어지는지 확인하는 것이다.

 

나누어떨어지지 않는다면 해당 수는 소수인 것이고, 도중에 다른 수에 의해 나누어 떨어진다면 그 수는 소수가 아닐 것이다.

 

 

2,3,4, ... , n - 1 

 

def is_prime(n):
    for i in range(2, n):
        if n % i == 0:
            return False # i로 나누어 떨어지면 소수가 아니므로 False 리턴
    
    return True # False가 리턴되지 않고 for문을 빠져나왔다면 소수이므로 True 리턴

 

 

위 방식은 입력값으로 받는 숫자 X에 대하여 2 ~ n-1번까지, 즉 n-2 번의 연산이 필요하며 이는 시간복잡도 O(x)로 표현할 수 있겠다.

 

 

하지만 약수의 특성을 활용해서 이 연산 횟수를 반으로 줄일 수 있다.

 

**약수의 특성이란, 특정 수 n의 약수들을 일렬로 나열했을 때 그 중 가운데의 수를 중심으로 약수가 대칭된다는 것이다.

 

36을 예로 들어보자.

 

16의 약수들을 일렬로 나열하면 1, 2, 3, 4, 6, 9, 12, 18, 36이 된다.

 

중간값 6를 기준으로 양 옆을 보면 약수들이 서로 대칭되고 있음을 확인할 수 있다.

 

(1 * 36 = 18 * 2 = 3 * 12 = 4 * 9 = 6 * 6)

 

만약 우리가 36의 약수를 찾고 싶다면 36의 약수의 중간값을 기준으로 한 쪽만 검사를 하더라도 다른 쪽의 약수들을 알 수 있다.

 

즉, 중간값은 찾고자하는 수의 제곱근 값 (sqrt 함수를 이용) 으로 가정해 처리할 수 있으며, 이 제곱근 값을 기준으로 왼쪽에 약수가 하나도 존재하지 않는다면 제곱근 값 기준 오른쪽에도 약수가 존재하지 않는다고 확신한다.

 

 

시간복잡도를 고려한 풀이

# 제곱근을 구하기 위해 math 라이브러리 임포트
import math

def is_prime(n):
    for i in range(2, int(math.sqrt(n))+1): # n의 제곱근을 정수화 시켜준 후 + 1, range함수 특성
        if n % i == 0:
            return False

    return True

 

 

---

#1. .split() 사용

문자열 나누는 방법, 집합안에 결과가 표현됨

>>> a = "Life is too long"
>>> a.split()
['Life', 'is', 'too', 'long']

>>> b = "a:b:c"
>>> b.split(':')
['a', 'b', 'c']

 

split 함수는 a.split() 처럼 괄호 안에 아무 값도 넣어 주지 않으면 공백(스페이스, 탭, 엔터 등)을 기준으로 문자열을 나누어 준다.

 

만약 b.split(':')처럼 괄호 안에 특정 값이 있을 경우에는 괄호 안의 값을 구분자로 해서 문자열을 나누어 준다.

 

이렇게 나눈 값은 리스트에 하나씩 들어가게 된다. ['Life', 'is', 'too', 'long'] 이나 ['a', 'b', 'c']에서 split 적용해보기 끝