[백준] 알고리즘 수학 - 나머지연산, GCD, LCM, 진법변환, 소수

• (a+b)%c = (a%c + b%c)%c
• (a*b)%c=(a%c * b%c)%c

• 나누기의 경우 성립하지 않는다.
• 뺄셈의 경우 음수를 대비해야한다.
• (a-b)%c=((a%c-b%c)+c)%c

---

GCD - 최대공약수 두 수 A와 B의 공통된 약수 중에서 가장 큰 정수이다.

LCM - 최소공배수 두 수의 공통된 배수 중에서 가장 작은 정수이다.

 

유클리드 호제법 - GCD(a,b) = GCD(b,a%b)

a%b의 값이 0이될때의 b의 값이 최대공약수이다.

 

---

소수 - 약수가 1과 자기 자신만 있는 수를 뜻한다.

• 소수는 2보다 크거나 같고, 소수-1보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

for(int i=2;i<=n-1;i++)

시간복잡도는 O(N)

 

• 소수는 2보다 크거나 같고, 소수/2보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

소수의 약수 중에서 가장 큰 것은 n/2보다 작거나 같다.

소수는 x*y로 나타낼 수 있는데 x가 2라고 생각하면 y는 소수/x(2) 라고 생각하면 된다.

for(int i=2;i<=n/2;i++)