유클리드 호제법 썸네일형 리스트형 [c++][백준 21919][에라토스테네스의 체][유클리드 호제법] 소수 최소 공배수 - 컴도리돌이 21919번: 소수 최소 공배수 수열 중에 소수는 2, 3, 5가 있다. www.acmicpc.net 풀이과정 1. 주어진 입력 값중에서 소수가 존재하는지 판정한다. -> 에라토스테네스의 체를 이용하여 소수를 찾는다. 에라토스테네스의 체 : 소수란 약수가 오로지 1인 수이다. 즉, 1을 제외한 수의 배수가 되는 수는 소수가 아니다. 에라토스테네스의 체는 이러한 소수의 개념을 이용한 알고리즘으로 임의의 수 n까지의 소수르 구하고자 할 때 2부터 n의 제곱근까지 돌며 모든 배수들을 소수에서 제외시키는 방식이다. 시간 복잡도 : O(Nlog(logN)) 2. 소수가 존재할 경우 -> 유클리드 호제법을 이용하여 최대 공약수를 구한다. 시간 복잡도 : O(log(N)) 3. 주의 사항 : 최소 공배수의 크기를 고.. 더보기 이전 1 다음
