[단계별로 풀어보기] 기본 수학 2 - 소수 찾기 (1978)

 

1978번: 소수 찾기 (acmicpc.net)

소수는 1과 자기 자신 외에는 나눌 수 있는 수가 없는 수를 의미한다.

그런 수를 찾기 위해서는 세가지 방법이 있다.

 

소수 판별하기

방법 1. n까지 나눠보기

n = int(input())
isSo = True
for k in range(2, n):
    if (n%k) == 0:
        isSo = False

if isSo == True:
    print(n,"은 소수")
else:
    print(n,"은 합성수")

가장 원초적인 방법으로 for문을 돌려서 n까지의 수로 n을 나눠보는 것이다.

시간복잡도는 O(n)이 된다.

방법 2. n/2까지 나눠보기

n = int(input())
isSo = True
for k in range(2, int(n/2)):
    if (n%k) == 0:
        isSo = False

if isSo == True:
    print(n,"은 소수")
else:
    print(n,"은 합성수")

n의 절반 이상을 넘어가면, 어차피 그 수로는 n을 만들 수 없다.

따라서 n/2까지만 for문을 작성해도 된다.

시간복잡도는 O(n)이다.

방법 3. n의 제곱근까지 나눠보기

import math

n = int(input())
isSo = True
for k in range(2, int(math.sqrt(n))):
    if (n%k) == 0:
        isSo = False

if isSo == True:
    print(n,"은 소수")
else:
    print(n,"은 합성수")

어떤 수 n의 인수들을 나열해보면, 그 인수들의 중간값이 n의 제곱근보다 같거나 작은 것을 볼 수 있다.

따라서 n의 제곱근까지만 for문을 돌려도 n이 소수인지를 판별할 수 있다.

실제 로직 구현하기

n = int(input())
m = list(map(int, input().split()))
count = 0
for num in m:
    isSo = True
    if num == 1:
        isSo = False
    for i in range(2, num):
        if (num % i == 0):
            isSo = False
    if isSo == True:
        count += 1

print(count)

1이 들어오는 경우, 1은 소수가 아니므로 False를 넣어준다.

import math

n = int(input())
m = list(map(int, input().split()))
count = 0
for num in m:
    isSo = True
    if num == 1:
        isSo = False
    for i in range(2, int(math.sqrt(num)+1)):
        if (num % i) == 0:
            isSo = False
    if isSo == True:
        count += 1

print(count)

이렇게 해도 된다.