목록에라토스테네스 (1)

코딩뚠뚠

[기본문제풀이] 에라토스테네스의 체

풀이 일시 : 2020-08-13 ​ 에라토스테네스의 체 : 소수(prime number) 판별 알고리즘이다. 어떤 수로도 나뉘어지지 않아야 되기 때문에 그 수를 나눠보면서 판단할 수 있다.. -> 이 방법은 O(N)의 복잡도를 갖는다. 모든 수를 체크했기 때문이다. 제곱근까지만 약수의 여부를 검증한다 -> 이 방법은 O(N^(1/2))로 계산이 가능하다. -> int end = (int)sqrt(x)로 두고 x의 소수를 구하려면 2~end까지 체크한다. ​ 문제 : 에라토스테네스의 체를 이용하여 소수를 출력하여라. ​ 풀이 : 1. 이차원 배열을 생성하여 값을 초기화한다. 2. 2부터 시작해서 특정 숫자의 배수에 해당하는 숫자들을 모두 지운다. (자신은 지우지않는다.) 3. 3의 배수도 지운다. (자신..
알고리즘 문제풀이/기본문제풀이 2020. 12. 28. 00:38
이전 Prev 1 Next 다음