프로그래머스1 [Programmers][Python] 소수 찾기 1. 시간 초과 n 이하의 소수 개수를 찾는 문제이다. n이 1000000 이하의 자연수라 처음 한 방법은 시간초과가 났다. list를 계속 만들어서 그런가? def solution(n): prime = list(range(2, n + 1)) for i in range(2, n + 1): if i in prime: prime = list(filter(lambda x : x % i != 0 or x == i, prime)) return len(prime) # 시간 초과 2. 정답 bool list를 만들고 에라토스테네스의 체를 이용하여 풀었다. prime의 i번째 원소가 수 i이고, prime[i]가 true이면 i는 소수이다. 만약 i가 소수라면 j = 2 * i, 3 * i, 4* i ..... 2023. 12. 29. 이전 1 다음
