[Python] 소인수 분해하기 안녕하세요 파이썬으로 소인수를 분해하는 코드를 작성해보았습니다. ### 소인수 분해 ? 합성수를 소수의 곱으로 나타내는 것입니다. 6 합성수는 2 x 3 18 합성수는 2 x 3 x 3 51 합성수는 3 x 17 위 예시와 같이 소수로만 나타내는 작업입니다. def get_prime_factor(num): from collections import defaultdict dic=defaultdict(int) d=2 while d 알고리즘 2021.01.02
[Python&SQL] 소수(Prime number) 구하기 안녕하세요 이승혁 입니다. 이번 시간에는 소수(Prime number)를 구하는 알고리즘을 공부해보도록 하겠습니다. ### 소수(Prime number) ? 위키피디아 정의 : 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. 좌측은 소수(prime), 우측은 합성수(compoisite) 입니다. 좌측의 2, 3, 5, 7, 11 은 1과 자기 자신외에는 약수가 없습니다. 우측의 2, 4, 6, 8 ,9 10, 12 는 약수가 2개 이상입니다. ### 소수 구하는 방법 ? 1. 약수의 개수 특징 중 약수를 자신과, 1 두 개 만을 갖는다는 것을 알았습니다. 이를 사용해서 약수의 개수를 가지고 소수를 판별할 수 있습니다. 그래서 짜본 알고리즘은 약수의 개수로 접근을 해보려합니다... 알고리즘 2020.12.29
