에라토스테네스의 체
Goal 1. 소수 정의하기 2. 소수 찾는 알고리즘 - "에라토스테네스의 체" 이해하기 소수란? 소수란 숫자 중 나 자신과 1로만 나눠지는 수다. 즉, 그 2개의 수 이외의 다른 수로 나눠진다면 소수가 아닌 "합성수" 라고 말할 수 있다! 예시) 소수 : 2, 3, 5, 7, 11, 13, 17, 19, ... 그 외 : 4 (2로 나눠지니까), 6 (2와 3으로 나눠지니까), 8 (2로 나눠지니까), 9 (3으로 나눠지니까), ... "에라토스테네스의 체"는 언제 필요한가? N이라는 숫자가 소수인지 아닌지 판단하기 위해서는 2부터 N/2 까지의 숫자로 나눠봐야 알 수 있다 하지만 2부터 100까지의 숫자 중에서 소수를 출력하라고 한다면 이중 for문을 돌려야하고 시간 복잡도는 O(n^2)으로 느리다 ..
2023. 2. 13.
