나머지 연산

안녕하세요 오늘은 나머지 연산에 대해 말씀드리겠습니다. 백준 알고리즘을 참고했습니다.

 

나머지연산

1. 나머지로 출력하라는 문제가 등장할 때

2. (A+B) % M = ((A%M) + (B%M)) % M 

3. (A * B) mod M = ((A mod M) * (B mod M)) mod M

4. 나누기의 경우에는 성립하지 않음(Modular Inverse를 구해야 함)

5. 뺄셈의 경우에는 먼저 mod연산을 한 결과가 음수가 나올 수 있기 때문에 6번과 같이 해야함

6. (A - B) Mod M = ((A mod M) - (B mod M) + M) mod M

ex) (5+2) % 3 = 7 % 3 = 1 , (5 % 3 + 2 % 3) % 3 = 1, (2 + 2) % 3 = 4 % 3 = 1

 

그러면 

(6 % 3 - 5 % 3 ) % 3 = ( 0 - 2 ) % 3 = -2 % 3 = ? 

답이 무엇일까요??? -2 일까요 1 일까요 ?? 

 

 

답 : 프로그램마다 다릅니다. 자바 ,C는 -2가 나오지만 파이썬은 1이 나옵니다.

 

그러면 똑같이 나오게 할려면? 

 

 -> (a - b) % c -> (a % c - b % c + c) % c를 해주면 됩니다. 그러면 똑같은 답이 나옵니다. 

 

 

소수 

소수 : 약수가 1과 자신 밖에 없는 수

 

1.N이 소수가 되려면, 2보다 크거나 같고, 루트N 보다 작거나 같은 자연수로 나누어 떨어지면 안 된다.

이유는? N이 소수가 아니라면, N = a X b로 나타낼 수 있다(a <= b)

 

2. a > b라면 두 수를 바꿔서 항상 a <= b로 만들 수 있다.

3. 두 수 a와 b의 차이가 가장 작은 경우는 루트 N이다.

5. 즉, 루트 N까지만 검사를 해본다. 

 

 

관련 문제 : 소수찾기, 에라토스테네스의 체, 골드바흐의 추측, 팩토리얼 0의 개수 

 

 

이상 포스터를 맞치겠습니다.