소수 판정법
합성수 n에서 1을 제외한 가장 작은 약수는 n의 제곱근이다.
-> 2부터 n의 제곱근까지의 수로 나눴을 때 나누어지지 않으면 소수!
범위 내 소수 판정법 = 에라토스테네스의 체
고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법.
이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다.
- 배열을 생성하여 초기화한다.
- 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.(지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.)
- 2부터 시작하여 남아있는 수를 모두 출력한다.
소인수 분해
2부터 n까지
나눠지면 소인수 목록에 넣기
아니면 1만큼 증가
최대공약수 = 유클리드의 호제법
두 수 A, B에 대해서 A를 B로 나눈 나머지를 r이라고 하면 GCD(A, B) = GCD(B, r)이다.
최소공배수
A ⨉ B = GCD(A, B) ⨉ LCM(A, B) 성질 이용
이항계수
이항계수의 성질 nCk = n-1Ck-1 + n-1Ck을 이용하면 DP로 간단히 해결
팩토리얼에서 0의 개수
n!에 5가 하나 포함되면 0이 하나 생긴다
n!에서 곱하는 수들 중 5의 개수가 0의 개수와 같다고 보면된다
이때 25, 125와 같이 5의 n승은 5를 n개 가지므로 또 세어줘야함
따라서 n!에서 0의 개수는 n/5 + n/5^1 + ...+ n/5^k (5^k <= n)
30의 배수 조건
- 일의자리가 0
- 각 자리 수 합이 3의 배수
공부한 내용은 바로바로 기록하자!