먹고 기도하고 코딩하라

[백준] 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
반응형

'자료구조&알고리즘 > BOJ' 카테고리의 다른 글

[백준] 1978 : 소수 찾기 (파이썬)  (1) 2021.09.07
1 Comments
댓글쓰기 폼