알고리즘 기초 - 수학1

- 골드바흐의 추측

-> 2보다 큰 모든 짝수는 두 소수의 합으로 표현이 가능하다.

* 아직 증명 되지는 않았지만 10^18 이하에서는 참인것으로 증명 되어있다.

 

백만 이하의 짝수중 임의의 숫자 N = a+b(a,b는 소수)를 만족하는지 검증하는 문제.

 

에라토스테네스의 체를 이용하여 Check[N-b]가 false인지 판별하면 된다.

*N-b가 소수이면 a는 자동으로 소수가 되기 때문이다.

 

 

- 팩토리얼

N! = 1 x 2 x 3 .... x N

ex) 10! = 3628800

 

* 팩토리얼 0의 갯수문제

임의의 수 N!에서 0이 몇 개 인지 알아내는 문제.

ex) 10! = 3628800 -> 0이 2개.

 

c++ 또는 java에서 이를 실제로 계산하여 count 하면 시간이 엄청 오래걸리게 된다.

-> 소인수 분해하여 0의 갯수를 구한다.

0을 만들 수 있는 방법은 2 x 5 가 있어야 한다!

따라서 소인수 분해하여 2 x 5가 몇개 있는지 찾아내면 0의 갯수를 알아 낼 수 있다.

 

여기서 중요한점은, 2는 모든 짝수가 지니고 있기 때문에 갯수가 5에 비하여 많다.

따라서 2와 5의 짝의 갯수를 알아내려면 5의 갯수만 세어주면 된다.

 

이를 이용하여 실제로 소인수분해를 하지 않고 5의 갯수만 찾아주는 알고리즘을 짠다.

 

100!의 5의 갯수 구하기

100/5 = 20, 100/25 = 4 이므로  20+4 = 24개이다.

실제로 100!의 0의 갯수또한 24개로 나타난다.