에라토스테네스의 체를 이용한 빠른 소인수분해 에라토스테네스의 체(The Sieve of Eratosthenes)를 아직 모른다면 저의 이전 포스팅을 참고하시기 바랍니다.(http://plzrun.tistory.com/entry/폐구간1n-소수-구하기-에라토스테네스의-체-The-Sieve-of-Eratosthenes) [1,N]값에 대해 소수인지 판별하는 방법인 '에라토스테네스의 체'를 이용하면,[1,N]값에 대해 소인수분해를 빠르게 할 수 있다. 방법은 매우 간단하다.1부터 N까지 가장 작은 인수(factor)를 에라토스테네스의 체를 이용하여 구하는 것이다.이 값을 minFactor라 하자. (어떤 값 x의 minFactor는 minFactor[x]로 나타낸다.)그러면 임의의 x값을 소인수 분해하.. Algorithm/Mathematics 7년 전
폐구간[1,n] 소수 구하기 (에라토스테네스의 체 - The Sieve of Eratosthenes) 소수를 일반적인 방법으로 구한다면 아래와 같이 구할 수 있다.어떤 값 N이 소수임을 판별하기 위해서는 2부터 N-1까지의 수로 나눠보면 된다.이는 O(N)의 시간복잡도를 갖는다. 만약 1부터 N까지의 숫자가 소수임을 판별하기 위해서는위와 같은 방법으로는 만큼의 시간이 걸린다. 이보다 빠른 방법은 없을까?그 방법이 '에라토스테네스의 체'이다. (시간복잡도는 이다.) 1부터 10만까지의 숫자중에 소수인 숫자를 골라내려고 할 때,에라토스테네스의 체를 이용하여 구하는 방법은 아래와 같다. 2부터 시작한다.2는 소수인데, 2x (x>1)는 소수가 아니다.그러므로 우리는 2를 약수로 갖는 모든 숫자를 체크할 수 있다.이는 소수가 아닌 숫자를 체크하는 것인데,간단하게 C++.. Algorithm/Mathematics 7년 전
