primality test (2) 썸네일형 리스트형 49. Sieve of Eratosthenes 에라토스테네스의 체(Sieve of Eratosthenes)는 구간 내의 소수를 빠르게 찾아야 할 때 사용되는 방법이다. 이것을 이용하면 여러 개의 수를 동시에 소인수분해하는 것도 가능하고, 더 응용하면 약수의 개수나 약수의 합 등을 빠르게 구하는 것도 가능하다. 에라토스테네스의 체를 이용하여 소수를 찾는 과정은 다음과 같다. 일단 소수를 구하려는 범위 내의 수를 차례로 나열한다. 여기서는 n=120이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 4.. 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 다음
