코딩테스트/알고리즘
[알고리즘] 에라토스테네스의 체 with '프로그래머스 2단계 - 소수찾기 문제'
"에라토스테네스의 체" 알고리즘 문제, 특히 완전 탐색 유형을 풀다보면 아래와 같은 문제상황을 종종 마주친다. 1~n 사이에 있는 소수의 개수 구하기 보통 브루트포스를 통해 풀 수 있는데 레벨이 어느정도 되는 문제라면 시간초과가 발생하기 마련이다. 브루트포스(Brute Force)란? 직역하면 "무식한 힘" 이라는 뜻을 가진 알고리즘으로 무식하게 전체를 탐색하는 문제이다. 프루트포스를 사용하여 소수찾기 문제를 해결하면 아래와 같은 코드를 얻을 수 있다. 브루트포스 소수찾기 코드 def findSosuBF(n): sosuArr = [] for i in range(2,n+1): cnt = 0 for j in range(2,i): if i % j == 0: cnt+=1 if cnt == 0: sosuArr.a..
