prime factorization (1) 썸네일형 리스트형 48. Prime Factorization 소인수분해(Prime Factorization)는 양의 정수를 소수들의 곱으로 나타내는 것으로 다양한 문제에서 등장하는 개념이다. 소인수분해를 하는 방법은 다양하고 응용 범위도 넓은 편이기 때문에 각각의 상황에 맞는 소인수분해 방법을 선택하는 것이 좋다. 가장 간단한 소인수분해 방법은 다음과 같다.vectorv;void f(int n){ for(int i = 2; i $2$ 이상 $n$ 이하의 모든 정수를 확인하면서 $n$이 $i$의 배수이면 $i$를 소인수 목록에 추가하고 $n$을 $i$로 나눈 다음 계속 진행한다. 하지만 이 방법은 $n$이 $1$억 정도의 소수일 경우 성능이 상당히 떨어진다. 다행히도 위의 코드를 조금만 수정하면 성능은 매우 좋아진다.vectorv;void f(int n){ .. 이전 1 다음
