알골리즘1 [알고리즘] 에라토스테네스의 체 개요 에라토스테네스의 체는 소수를 판별하는 알고리즘입니다. 이해 * 설정 2 부터 N 까지의 Boolean 배열 생성, 초기값은 Truem^2 ≤ N 를 만족하는 자연수 중 가장 큰 m (M) 을 찾습니다. * 탐색 M이 1이거나 1보다 작으면 바로 탐색 종료 2 ≤ i ≤ M까지 순차 탐색배열 인덱스 i 값이 True 이면배열 인덱스 i 의 배수(2배, 3배, 4배…) 값을 모두 False 로 변경i 의 배수(2배, 3배, 4배…)가 N을 초과하기 전까지 반복탐색 과정 후 배열의 값이 True 인 배열의 인덱스는 소수다. 탐색 시 i 자기 자신은 업데이트하지 않습니다. (1배수 부터가 아니라 2배수부터 값 업데이트 ) 최적화 탐색 과정에서 i의 배수를 2의 배수부터가 아니라 i의 배수부터 탐색해도.. 2024. 9. 28. 이전 1 다음
