에라토스테네스의 체 (python 기본 구현)
def prime_list(n): # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주) sieve = [True] * (n+1) # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사 m = int(n ** 0.5) for i in range(2, m+1): if sieve[i] == True: for j in range(i+i, n+1, i): # i 배수는 소수 목록에서 제거(False) sieve[j] = False return [i for i in range(2, n+1) if sieve[i]] print(prime_list(20)) # [2, 3, 5, 7, 11, 13, 17, 19] - 관련 문제 참고: - 문제: programmers.co.kr/lear..
2020. 10. 22.
최대공약수(유클리드 알고리즘)와 최소공배수 찾기
- 유클리드 알고리즘: 최대 공약수 찾기 알고리즘 - 최대 공약수(GCD, Greatest Common Divisor): 1번: 재귀 함수 이용 def gcd(a, b): return a if b == 0 else gcd(b, a%b) print(gcd(6, 24)) # 6 2번: 재귀 함수 X def gcd2(a, b): gcd = 1 for k in range(2, min(a, b) + 1): while a % k == 0 and b % k == 0: a //= k b //= k gcd *= k return gcd def lcm(a, b): return a*b//gcd2(a, b) print(gcd2(14, 42)) # 14 print(lcm(14, 42)) # 42 - 출처: m.blog.naver..
2020. 10. 14.