소인수분해 하는 소스 코드 작성해봤는데요.

음.. 소인수분해는 분해하고자 하는 수의 sqrt() 보다 작은 2이상의 정수로 모두
나누어보아야 하는 거 아닌가요?

int getPrime(int FirstInputNumber, int arr[]) ;

어짜피 출력만 하고 끝나면 재미없으니깐,
답을 저장할 배열을 넘겨주고(배열의 크기는 부르는쪽에서 알아서 결정하기로 하고),
몇개의 prime number 가 나왔는지를 넘겨주면 훨씬 유용한 함수가 되지 않을까 생각합니다.

초보의 의견이었슴다.

2로 나누어 떨어지지 않을 때까지 나눈 후,
3부터 제곱근까지의 홀수로 나누어 가는 방식을 사용했습니다.
(속도가 약간 향상되지요.)

고정되어 있지 않은 여러개의 리턴값을 갖는 함수의 디자인은
다음과 같이 출력 반복자를 사용하면 간편합니다.

#include <iostream>
#include <iterator>

template <typename IntegerType, typename OutputIterator>
void prime_factor(IntegerType m, OutputIterator result)
{
    while (m % 2 == 0) {
        m /= 2;
        *result++ = 2;
    }
    if (m > 1) {
        for (IntegerType d = 3; m >= d * d; d += 2)
            while ((m % d) == 0) {
                m /= d;
                *result++ = d;
        }
        if (m > 1) *result++ = m;
    }
}

int main()
{
    int m;
    while (std::cin >> m) {
        prime_factor(m, std::ostream_iterator<int>(std::cout, " "));
        std::cout.put('\n');
    }
    return 0;
}

(defun factorize (n)
  (labels ((factor-aux (try num)
             (cond ((= try num)  (list try))
                   ((zerop (mod num try))
                    (nconc (list try) (factor-aux try (/ num try))))
                   (t (factor-aux (1+ try) num)))))
    (factor-aux 2 n)))

CL-USER 55 > (factorize 20)
(2 2 5)

(defun get-divisors (n)
  (loop for i from 2 to n
           when (zerop (mod n i)) collect i))

CL-USER 18 > (get-divisors 20)
(2 4 5 10 20)

http://groups.google.co.kr/groups?threadm=3F137DB7.5B957270%40bawi.org

구글에는 일부만 있군요. 이 쓰레드로 유즈넷에 있는 글은 대략 40개 쯤인데..

2하고 홀수로만 하니까 훨씬 빨라지네요.

 $ time factor 313418913
313418913: 3 104472971

real    0m0.010s
user    0m0.000s
sys     0m0.010s
 $ time ./factor 313418913
313418913: 3 104472971

real    0m1.794s
user    0m1.750s
sys     0m0.010s

하지만 여전히 GNU factor와 비교해서 엄청나게 느린속도.

FYI - GNU factor 에서 사용한 알고리즘

wheel factorization 을 사용한다고 되어있군요.

http://primes.utm.edu/glossary/page.php?sort=WheelFactorization

2 와 홀수로 나누는 것도 이 알고리즘이죠 사용 prime [2], wheel size = 2, 50% 정수를 건너 뜀.

GNU factor 에서는 [2,3,5,7,11] 다섯개의 prime 으로 wheel 을 만들고 480/2310 의 정수만 check 합니다. (2310-480)/2310 - 대략 79% 의 정수를 건너뜀.

다양한 프로그래밍언어로 작성된 소인수분해코드를 더 감상하고프신 분은 Project Euler Problem 3을 풀어서 로그인한 후 답안을 제출해보세요. 그러면 답을 맞춘 사람들만 접속할 수 있는 포럼이 나옵니다.

소인수분해하는 파이썬 코드.

def factors(n):
	"""produces factors
 
	>>> print factors(2 * 2 * 17 * 17 * 17)
	[2, 2, 17, 17, 17]
	"""
        list = []
        i = 2
        while 1:
                while n % i == 0:
                        list.append(i)
                        n = n / i
                if n == 1:
                        break
                elif i * i > n:   # n is products of primes that is > i
                        list.append(n)   # because n is prime, last one.
                        break
                i++
        return list

파이썬 모르는 분은 다음 세 가지만 알면 위 코드를 읽을 수 있다는...

"""에서 두번째 """까지는 주석.
#로 시작하는 부분도 주석.

factors(2 * 2 * 5 * 17 * 17)를 실행할 경우 list의 값과 n의 값은
[], 2 * 2 * 5 * 17 * 17
[2], 2 * 5 * 17 * 17
[2, 2], 5 * 17 * 17
[2, 2, 5], 17 * 17
[2, 2, 5, 17], 17
[2, 2, 5, 17, 17], 1
의 순서로 변화하고 총 나눗셈연산(/, %)은 O(17)번 실행됩니다.
일반적으로 n을 나누는 가장 큰 소수가 p일 때 p * p 가 n을 나누어 떨어지는 경우는 총 나눗셈연산횟수가 O(p)이고 p * p가 n을 나누지 않는 경우는 총 나눗셈연산횟수가 O(sqrt(p)).
이보다 빠른 알고리즘은 없을 것 같다는... 아 물론 i를 돌릴 때, 2가 아닌 짝수는 뛰어넘고 3이 아닌 3의 배수도 뛰어넘는 식으로 하면 더 빨라지긴 하지만, 그래도 O()는 불변.