[백준] 1978: 소수 찾기

소수를 구하는 문제였다.

풀이

def isPrime(data):
    cnt = 0
    for i in data:
        for j in range(2, i + 1):
            if i % j == 0:
                if j == i:
                    cnt += 1
                break
    print(cnt)


n = int(input())
data = list(map(int, input().split()))
isPrime(data)

위에서 사용한 코드의 설명을 들어보겠다. 예를 들어 3이라면 (입력값 = 1 \n 3)

i = 3 j = 2(에서 4까지 증가)

만약 i % j 가 나누어떨어진다면, i 와 j 가 같은지 비교, 같다면 카운트 증가(= 소수이다)

이므로 3일경우 3 % 3이 될 때 3 == 3이므로 카운트는 증가할 것이다.

트러블 슈팅 (해결)

처음에 데이터 입력을

n = int(input())
for i in range(n):
    num = int(input())
...

이런식으로 받으려고 했었는데, 저 형태를 유지하면서 space로 하나씩 입력받는 법을 몰라서 다시 list map으로 변경했다.

그리고 소수를 원래는 제곱근을 이용해서 풀려고 했어서 int(math.sqrt(i))를 시도했는데, 제곱근으로 푸는 것이 더 잘 안돼서 그냥 2 ~ 그수 + 1 까지 for문을 돌렸다. 나누어떨어질때 그 수와 for 문 내 변수(j)가 같으면 소수이다 라는 방법으로 시도하였다. 근데 제곱근을 쓰면 O(n^2)에서 O(√n)까지 줄일 수 있을거 같아서 좀 아쉽다.

 

이는 이후 푼 문제인 소수 구하기에서 사용한 제곱근 방식을 통해 해결했다!

def isPrime(data):
    cnt = 0
    for i in data:
        if i <= 1:
            continue
        for j in range(2, int(i ** 0.5) + 1):
            if i % j == 0:
                break
        else:
            cnt += 1
    print(cnt)


n = int(input())
data = list(map(int, input().split()))
isPrime(data)

최종 코드

최종 코드는 위에 기재한 두가지 모두이다. 왜냐면 결국 시간복잡도는 이중 for문으로 인해 O(n^2)라서, 비슷한 결과를 가져올 것 같다.