Modular Arithmetic모듈러 연산은 어떤 수를 특정한 값(모듈러, modulus)으로 나눈 나머지를 계산하는 연산으로, 쉽게 말해 나머지 연산이다.A mod B = RA : 나눠지는 수 (피제수, Dividend)B : 나누는 수 (제수, Modulus)R : 나머지 (Remainder) 덧셈, 뺄셈, 곱셈의 모듈러 연산모듈러 연산에서 덧셈, 뺄셈, 곱셈은 분배 법칙을 따른다. 연산 후 모듈러를 취하는 것과, 각각 모듈러를 취한 후 연산하는 것이 동일하다는 뜻이다.덧셈(A + B) mod C = [(A mod C) + (B mod C)] mod C뺄셈 (음수가 나올 경우, C를 더해서 양수로 만들 수 있음)(A - B) mod C = [(A mod C) - (B mod C) + C] mod..

📍 에라토스테네스의 체소수를 찾는 방법으로 시간복잡도는 O(N^1/2)이다. 💡 원리1. 2부터 시작해 그 수의 배수를 모두 지운다.2. 배수를 지운 다음, 다음으로 남아 있는 수를 선택해 다시 그 수의 배수를 지운다.3. 반복한다.4. 남은 수는 소수이다.🥑 예시코드2부터 100까지의 소수를 구한다.isPrime이라는 boolean 배열을 사용해 소수 여부를 표시한다.배열의 길이는 100이며, 초기값은 모두 true로 설정한다.isPrime[0]과 isPrime[1]은 소수가 아니기 때문에 false로 설정한다.2부터 시작해, 현재 수 i가 소수(isPrime[i] == true)라면, 그 수의 제곱부터 시작해 해당 수의 모든 배수를 false로 설정한다.이는 배수들이 소수가 아니라는 것을 의미한..