백준 1929
2023. 11. 16. 07:23ㆍ알고리즘
소수의 조건: 약수가 1과 자신만 있어야 함. 다른 수로는 나뉘면 안 됨
♣ 첫 번째 시도
M 이상 N 이하의 수들을 하나씩 소수인지 아닌지 따져봄. 숫자가 1이면 소수가 아니므로 바로 break를 준다.
해당 숫자까지 모두 가져와서 나눌 필요 없이 (i // 2) + 1 까지만 가져와서 나누면 된다. 나누는 와중에 나머지가 0이 되면, 즉 약수가 1과 그 자신 외에도 존재하면 break를 준다. 끝까지 나머지가 0이 되는 경우가 없으면 해당 수는 소수이므로 출력한다.
-> 시간 초과!
♣ 두 번째 시도
시간 초과를 해결하기 위해 해당 수가 소수인지 확인하는 부분을 함수로 만들었음.
all: 파이썬에 내장된 함수. 반복 가능한(iterable) 객체의 모든 요소가 참(True)이면 True를 반환함. 그렇지 않으면 False를 반환함
is_prime 함수에서는 all은 지정된 범위 내의 모든 i에 대해 조건 num % i != 0이 참인지 확인하는 데 사용됨. 모든 i에 대해 나머지가 0이 아니면 True가 반환됨. if is_prime(i) 가 true를 반환하면 해당 수 i를 출력함.
♣ 질문
첫 번째 방법이나 두 번째 방법이나 for 문은 두 개씩 사용하는데 왜 두 번째 방법에서는 시간 초과가 나지 않는걸까?
'알고리즘' 카테고리의 다른 글
| 백준 1541번 잃어버린 괄호 (1) | 2023.12.06 |
|---|---|
| 백준 알고리즘 11659번(구간합 구하기) (1) | 2023.12.04 |
| 백준 1213번(팰린드롬 만들기) (1) | 2023.11.29 |
| 백준 1072번(이분탐색) python (1) | 2023.11.18 |
| 백준 알고리즘 1920번 (0) | 2023.11.08 |