소수

소수 판정법

• i를 N-1 까지 돌리지 않고, i^2 <= n 일때 까지만 확인
  ⇒ 시간복잡도 줄이기 : O(N) ⇒ O(√n)

에라토스테네스의 체

• N이하의 소수를 모두 찾는 방법

1. N칸짜리 배열 - 소수면 true, 아니면 false

• 1은 false, 나머지는 true로 초기화

2. i=2 부터 +1씩 해나가면서 i가 소수인지 확인 후, i의 배수들은 false로 저장한다.

• 최적화
  
  
  

소인수분해

1. i를 2로 초기화, 소인수 목록을 담을 배열 준비
2. N이 i로 나눠 떨어지는지 확인
   → 나눠떨어지면, 소인수 목록에 i를 추가, N을 i로 나눈다.
   → N이 i로 나눠떨어지지 않을 때 까지 반복
3. N이 i로 나눠떨어지지 않으면 i++
4. N==1 이면 알고리즘 종료
   

• 최적화
  i를 2 ~ N-1 까지 돌리지 않고, i^2 <= n 일때 까지만 확인
  ⇒ 시간복잡도 줄이기 : O(N) ⇒ O(√n)
• 주의
  N=1이 되었을 때, 1을 출력하지 않도록 주의
  

약수와 최대공약수

유클리드 호제법

GCD(56, 12)
= GCD(12, 8)
= GCD(8, 4)
= GCD(4, 0)
= 4

합동식

• 주의
  
  

연립합동방적식

이항계수와 팩토리얼

• 바킹독 - 수학