챌린저스 매일 인증 (4) 소수 찾기
❓문제
🤔 과정
- 총 3번의 시도
- (1) 이중 for문을 사용해 소수를 구했다.
- -> 3개의 예제에서 시간초과가 나고 효율성 테스트에서 계속 떨어짐
- (2) 2를 제외하고 홀수만 시도 (시간 감소를 위해)
- -> 같은 이유로 실패
- (3) 소수 구하기에서 시간복잡도가 루트 n으로 가장 적게드는 isPrime 함수를 따로 만들어 시도
- -> 같은 이유로 실패
이쯤 되니 이중 for문을 쓰면 안된다는 생각이 들었다.
그렇게 검색을 해서 발견한 개념
❗️에라토스테네스의 체
아마 에라토스테네스의 체로 효율성까지 챙기길 바랬던 것 같다.
🙋🏻♀️ 내 코드
def solution(n):
answer = set(range(2, n+1))
for i in range(2, n+1):
if i in answer:
answer -= set(range(2*i, n+1, i))
return len(answer)
Author And Source
이 문제에 관하여(챌린저스 매일 인증 (4) 소수 찾기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dawnofspring/챌린저스-매일-인증-4-소수-찾기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)