2.16 알고리즘3 수학

나머지

(A + B) % M = ((A%M) + (B%M)) % M
(A * B) % M = ((A%M) * (B%M)) % M
(A - B) % M = ((A%M) - (B%M)) % M <- 음수 주의

최대공약수 GCD

1. n1, n2가 있을 때 2부터 min(n1, n2)까지 반복하면서 구하는 방법
2. 재귀함수를 이용한 유클리드 호제법

   ```js

   const getGCD = (n1, n2) => {
   if(n2 === 0) {
   return n1;
   } else {
   return getGCD(n2, n1%n2)
   }
   }

   ```

최소공배수 LCM

최소공배수 = GCD (n1/GCD) (n2/GCD)

소수

약수가 1과 자기 자신밖에 없는 수
N이 소수가 되려면 2보다 크거나 같고, N-1보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

1. 소수인지 판별하기
   방법 1) 시간복잡도 O(N)

const check = (n) => {
	if(n < 2) {
    	return false
    }
    for (let i = 2; i < n; i ++) {
    	if(n % i === 0) {
        	return false
        } 	
  	}
    return true
}

방법 2) N = a * b 일 때 a의 최소값 = 2, b는 N/2보다 클 수 없다.
시간복잡도 O(1/2 N) === O(N)

const check = (n) => {
	if(n < 2) {
    	return false
    }
    for (let i = 2; i < n/2; i ++) {
    	if(n % i === 0) {
        	return false
        } 	
  	}
    return true
}

방법 3) 시간복잡도 O(루트N)

N = a * b
a <= b ? 두 수의 차이가 가장 작은 경우는 루트N

	const check= (n) => {
      if(n < 2) {
      	return false
      }
      for(let i=2; i*i<=n; i++) {
      	if(n % i === 0){
        	return false
        }
      }
      return true
    }

방법 4) 에라토스테네스의 체
적어두고 지워지지 않은 수 중 가장 작은 수의 배수를 지워감
2의배수,,,3의배수,,,

const arr = Array(n).fill().map((arr, i) => {return true})

for (let i = 0; i*i <= n; i++){
	if(arr[i]) {
      //배수를 false로 지우기
    	for(let j = i*i; j <= n; j += i){
          arr[j] = false
        }
    }
}
arr.splice(0, 2, false, false)

    const result = arr.filter((value) => {
        return value !== false;
    })
    
    return result.length;