📗 소수 찾기

코딩테스트에서 가장 먼저 접하는 소수 찾기 문제에 대해서 정리해 보려고 한다.

이를 알아보기 전에 먼저 약수와 소수를 정리해보자.

약수란 어떤 수 n이 있을 때, n을 나누어 떨어지게 하는 수를 n의 약수라고 한다. 예를 들면 n이 8일 때 n의 약수는 1, 2, 4, 8이 된다.

이러한 약수들 중에서 1과 자기 자신으로만 나누어 떨어지는 수를 소수라 한다.
8의 약수인 1, 2, 4, 8에서 소수를 찾는다면 2가 해당이 된다(참고로 1은 1과 자기 자신으로만 나누어 떨어지지만 1을 소수로 인정하면 소인수분해의 유일성이 깨지기 때문에 소수의 정의에서 1은 제외된다)

코드로 구현하기 (O(n))

def is_prime_number(n):
    for i in range(2, n): # 2부터 n-1까지 for문을 돌며 나누어 떨어지는지 확인
    	if n % i == 0:   # 나누어 떨어진다면 그 수는 소수가 아님
        	return False
    return True
print(is_prime_number(8))
print(is_prime_number(2))

출력결과

False
True

그러나 이 방법은 시간복잡도가 O(N)인 풀이인데, 코딩테스트 문제에서 사용하면 시간초과로 문제를 통과할 수 없다...

제곱근

n의 약수는 무조건 sqrt(n)의 범위에 존재한다.

n을 더 큰 숫자인 16으로 예시를 살펴보자.

16의 약수는
1 x 16
2 x 8
4 x 4
8 x 2
16 x 1 이다.

이를 자세히 살펴보면 4 x 4라는 가운데의 약수를 기준으로 등식이 대칭인 것을 확인할 수 있다. 대칭이라는 것은 쌍이 존재한다는 말이고, 제곱근(가운데의 약수)까지만 확인하면 n의 약수를 구하거나 소수인지 판별할 수 있다.

-> √16인 4를 확인했는데 1, 2, 4에 대응되는 쌍인 16, 8, 4를 얻을 수 있었기 때문에 √n까지만 확인한다면 소수인지 판별을 할 수 있다(√n까지 나누어 떨어지는 수가 없었다면 √n 이상의 수에서도 나누어 떨어지는 수가 무조건 존재하지 않는다)

코드로 구현하기 (O(√n))

def is_prime_number(n):
    for i in range(2, int(n**(1/2)+1)):
    	if n % i == 0:
        	return False
    return True
print(is_prime_number(8))
print(is_prime_number(2))

출력결과

False
True

에라토스테네스의 체

앞선 방법인 제곱근 풀이법으로 소수 판별을 진행하여 시간복잡도를 향상할 수 있었다. 하지만 이는 n의 값이 작을 때 효율적이며 소수판별을 해야할 수의 개수가 많아질수록 O(n√n)이 되기 때문에 여러 개의 수가 소수인지 판별하고 싶다면 에라토스테네스의 체 알고리즘을 사용해야한다.

에라토스테네스의 체 알고리즘은 굉장히 간단하다. 1에서 25까지의 수에서 소수를 구해보자.

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20
21	22	23	24	25

먼저 1은 소수가 아니니 2부터 시작해야 한다.
그리고 i가 소수일 때 i를 제외한 i의 배수를 모두 지운다.
-> 2부터 시작하였을 때 2를 제외한 배수를 모두 지운다.

0	2	3	0	5
0	7	0	9	0
11	0	13	0	15
0	17	0	19	0
21	0	23	0	25

다음 수인 3을 선택한다.
그리고 3을 제외한 3의 배수를 모두 지운다.

0	2	3	0	5
0	7	0	0	0
11	0	13	0	0
0	17	0	19	0
0	0	23	0	25

다음 수인 5를 선택한다.
그리고 5를 제외한 5의 배수를 모두 지운다.

0	2	3	0	5
0	7	0	0	0
11	0	13	0	0
0	17	0	19	0
0	0	23	0	0

코드로 구현하기 (O(nlog(logn)))

n=25
arr = [False,False] + [True]*(n-1) #처음에 0, 1 제외 모두 True로 세팅 

primes=[]

for i in range(2,n+1): #n까지 소수판별
  if arr[i]: #arr[i]가 True이면 소수
    primes.append(i) 
    for j in range(2*i, n+1, i): #a[i]의 배수를 모두 지움 
                                 #i가 2일때 4부터 2씩 더해가면서 지움
        arr[j] = False

print(primes)

소수 찾기 문제 풀어보기

백준 1978번 문제이다. 연습하는데에 도움이 될 것 같다.

import sys

N = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
sosu = 0
for i in range(N):
    test = 0
    if arr[i] > 1:
        for j in range(2, int(arr[i]**(1/2))+1):
            if arr[i] % j == 0:
                test += 1
        if test == 0:
            sosu +=1

print(sosu)