[기타] 코딩테스트에 활용되는 수학 이론

최대공약수와 최소공백수

최대공약수

// 유클리드 호제법
const gcd = (a, b) => {
	if(a % b === 0) {
        return b;
    }

    return gcd(b, a % b)
};

// 반복문
const gcd = (a, b) => {

	// 큰 걸 작은 걸로 나누고
    // 깔끔히 안나뉘었으면
    // 작은걸 => 큰걸로 / 나눈나머지 => 작은걸로 다시 재조정해서
    // 깔끔하게 나뉠 때 까지 반복 후 => 나머지가 없을 때 작은 값을 최대공약수로 한다
	while(a % b !== 0) {
    	[a, b] = [b, a % b]
    }
    
    return b;
}

최대공배수

// 최소공배수 = (a * b) / 최대공약수

const gcd = (a, b) => {
	if(a % b === 0) {
        return b;
    }

    return gcd(b, a % b)
};

const lcm = (a, b) => {
  return a * b / gcd(a, b)  
};

---

소수체크

이 방법은 코테에서 시간 복잡도가 크기 때문에 느려서 틀리다고 나올 수 있다. => 에라토스테네스의 체 개념을 이용

const isPrime = (num) => {
    for(let i = 2; i < num; i++) {
        if(num % i === 0) {
            return false
        } 
        if(i * i > num) {
            break;
        }
    }

    return true;
}

 

에라토스테네스의 체

const findPrimes = (num) => {
	const numArr = new Array(num + 1);
	numArr.fill(true);
	numArr[0] = numArr[1] = false;

	for (let i = 2; i <= Math.sqrt(num); i++) {
		for (let j = 2; i * j <= num; j++) {
			numArr[i * j] = false;
		}
	}

	return numArr.reduce((acc, val, ind) => {
		if (val) {
			return acc.concat(ind);
		} else {
			return acc;
		}
	}, []);
};