먹고 기도하고 코딩하라

[백준] 1978 : 소수 찾기 (파이썬) 본문

자료구조&알고리즘/BOJ

[백준] 1978 : 소수 찾기 (파이썬)

2G Dev 2021. 9. 7. 08:42
728x90
728x90

 

 

1978번: 소수 찾기

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

www.acmicpc.net

문제 설명

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

 

입력

 

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

 

출력

 

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

 

 

3주 전쯤 푼 문제인데 왜 틀리는지 몰라서 많이 틀렸던 문제다.

먼저 틀린 코드부터 살펴보자.

 

input()
l = list(map(int, input().split()))
cnt = 0

for x in l:
  if x <= 1: continue
  for j in range(int(x // 2)+1, 1, -1):
    if not bool(x % j): break
  else:
    cnt += 1

print(cnt)

일단 주어지는 수 n은 필요없어서 안 받았다. 어차피 split할 때 아무 영향도 못 주니까.

x가 1보다 작으면(1000 이하의 자연수이니 1이면) 그냥 넘어가게 만들었다. 1은 소수가 아니다.

그 다음 x를 2로 나누고 버린 수에 1을 더한 다음, 1까지 -1씩 감소하면서 x % j가 없으면 break를 하게 만들었다.

bool로 써서 더 헷갈린다는 사실을 깨닫고 이번에는 for j 루프 안을 다시 짰다.

 

input()
l = list(map(int, input().split()))
cnt = 0

for x in l:
  if x <= 1: continue
  for j in range(2, int(x ** 1/2)+1):
    if x % j == 0: break
  else:
    cnt += 1

print(cnt)

이번에는 2부터 시작해서 x의 제곱근에 나머지를 버리고 1을 더한 수까지 비교하도록 만들었다.

예를 들어 주어진 수 x가 17일 때, 위의 코드는 9까지 검사하지만 이 코드는 5까지만 검사한다. 이 코드가 더 효율적인데, 이유는 어차피 소수가 아닐 거라면 제곱근 범위 안에서 약수가 나와 걸러지기 때문이다. (16의 약수는 1, 2, 4, 8, 16인데 이미 제곱근 범위 안에서 약수가 다 나왔다.)

또한 x % j == 0일 때, 즉 나누어 떨어지면 소수가 아니므로 중단하도록 했다.

for-else 문에서 else 문은 for 문이 중간 break 없이 정상 종료되었을 때 실행된다. 이런 소수 찾기 등에서 유용하게 쓰이는 구문이다. for 루프에서 중간 탈출이 없었다면 나누어 떨어지는 수가 없는 소수라는 뜻이므로 cnt에 1을 더해준다.

간단한 논리인데 엄청 많이 틀려서 결국 남의 코드를 참고한 문제였다.

 

 

728x90
반응형
1 Comments
댓글쓰기 폼