Algorithm/Basic
-
[Python] 에라토스테네스의 체 (Sieve of Eratosthenes)Algorithm/Basic 2021. 4. 4. 22:00
1. 정의 - 2부터 시작하여, 소수인 경우 값을 출력하고, 해당 소수의 모든 배수들을 소거해 나가는 방법 2. 방법 - 2 -> 소수, N보다 작은 모든 2의 배수 제거 - 3 -> 소수, N보다 작은 모든 3의 배수 제거 - .... - k -> 소수, N보다 작은 모든 k의 배수 제거 예를들어, 20까지의 소수 구하기를 한다면, 2의 배수부터 20까지의 배수를 지워주는 방식이다. import time def isPrime(v): i = 2 while i*i = 2: primeList = list..
-
[Python] 유클리드 호제법(Euclidean Algorithm)Algorithm/Basic 2021. 3. 19. 18:46
1. 정의 - 두 수의 최대공약수를 구하는 알고리즘 2. 방법 - 2개의 자연수 a, b(a > b) 에 대해서 a를 b로 나눈 나머지를 r이라 하면, a와 b의 최대 공약수는 b와 r의 최대공약수와 같음 -> 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수가 된다. 3. 비교 유클리드 호제법이 아닌 다른 방법으로 코드를 작성한 후, 시간을 비교해보았습니다. 2초 가량 차이가 난다. 결론: 최대공약수를 구할 땐 유클리드 호제법을 이용하자