[백준] 1978 소수 찾기 python 알고리즘 문제

문제 1978. 소수 찾기

1. 나의 코드와 발상 과정

## 오답

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

ans = 0
for i in range(n):
    a = num_list[i]
    if a == 2 or a == 3 or a == 5 or a == 7:
        ans += 1
    elif a == 1 or a % 2 == 0 or a % 3 == 0 or a % 5 == 0 or a % 7 == 0:
        continue
    else:
        ans += 1

print(ans)

1은 소수가 아니다.

소수는 1과 자기자신만을 약수로 가지는 수이다.

그렇다면 소수가 아닌 수에 공통적으로 들어가 있는 소수는 무엇일까?

아 2, 3, 5, 7이 있지 않을까.

그러면 2, 3, 5, 7로 나누어 떨어지지 않으면 카운트 해야겠다.

 

라고 생각하고 짠 코드다.

 

문제를 풀 당시에는 전혀 생각하지 못하고, 고치지 못했는데

생각해보니 1, 11, 121을 약수로 가지고 있는 121부터 소수를 골라내지 못하는 것을

위에 5줄 정도의 포스팅을 쓰면서 알게 되었다.

 

(정말 멍청한데?)

 

2. 고수님의 깔끔한 코딩

n = int(input())
num_list = list(map(int, input().split()))
ans = 0

for num in num_list:
    if num == 1:
        continue
    no_prime = 0
    for i in range(2, num):
        if num % i == 0:
            no_prime += 1
            break
    if no_prime == 0:
        ans += 1

print(ans)

1일 경우 continue하고,

2이상의 수가 입력될 경우, 2부터 모든 경우의 수를 서칭해준다.

no_prime이라는 변수를 두고, 이 수가 소수인지 아닌지를 판별해주고, 어떤 수로도 나누어지는 소수가 아닌 수면 no_prime을 +1 하고 그 다음 조건문에서 no_prime == 0 일 경우만 소수의 개수를 세는 ans에 +1 해준다.

 

한 마디로 그 2부터 그 수까지 전체 수를 나누어 보는 것이다.

 

3. 아쉬운 점

나의 짧은 생각

 

 

 

 

문제 출처

https://www.acmicpc.net/problem/1978