최대공약수 최소공배수 소수

function solution(n) {
    var arr = [];
    for (var i = 0; i < n + 1; i += 1) {
        arr.push(true);
    }
    
    for (var i = 2; i * i <= n; i += 1) {
        if (arr[i]) {
            for (var j = i * i; j <= n; j += i) {
                arr[j] = false;
            }
        }
    } 
  
    arr.splice(0, 2, false, false);    
    var result = arr.filter((value) => {
        return value !== false;
    })    
    return result.length;
}​

// 최대공약수
function GCD(value1, value2) {
  // value1과 value2 중 큰 값을 기준으로 값을 선택
  let num = value1 > value2 ? value1 : value2;

  let max;
  for (let i = 1; i <= num; i++) {
    if (value1 % i === 0 && value2 % i === 0) {
      max = i;
    }
  }
  return max;
}

위 아래는 같은데 min과 max를 구하는 방법만 다르다.

// 최대공약수
function getGCD (a, b) {
    let gcd = 0;
    for(let i = 1; i <= Math.min(a, b); i++) { 
      if ((Math.min(a, b)%i == 0) && (Math.max(a, b)%i == 0)) gcd = i;
    }
}

 

// 최소공배수
function getLCM (a, b) {
    let lcm = 1;
    while(true){
      if((lcm % a == 0) && (lcm % b == 0)){
        break;
      }
      lcm++;
    }
    return lcm;
 }

 

 

 

* 유클리드 호제법으로 구하기 - ① 재귀 함수

function gcdlcm(a, b) {
    var answer = [];
    var minNum = Math.min(a, b);
    var maxNum = Math.max(a, b);
    answer[0] = gcd(minNum, maxNum);
    answer[1] = lcm(minNum, maxNum);
    return answer;
}
// 최대공약수
function gcd(minNum, maxNum){
  return (minNum % maxNum) === 0 ? maxNum : gcd(maxNum, minNum % maxNum);
}
// 최소공배수
function lcm(minNum, maxNum){
  return minNum * maxNum / gcd(minNum, maxNum);
}

function getGCD (a, b) {return b ? getGCD(b, a % b) : Math.abs(a);}
function getLCD (a, b) {return (a * b) / getGCD(a, b);}

// 최대공약수
function gcd(a, b) {
    if (a % b == 0) {
        return b;
    } else {
        return gcd(b, a % b);
    }
}

// 최소공배수는 (a * b) / gdc

function solution(n, m) {
    var answer = [];
    var biggerNumber = Math.max(n,m);
    var smallerNumber = Math.min(n,m);
    
    // gcd
    function calGcd(a,b) {
      if (b === 0){
        return a;
      }
      return calGcd(b, a%b)
    }
  
    var gcd = calGcd(biggerNumber,smallerNumber ); 
   
    // lcm
    var lcm = (m * n) / gcd;

    answer[0] = gcd;
    answer[1] = lcm;
  
    return answer;
}

 

 

* 유클리드 호제법으로 구하기 - ② 반복문

// 최소공배수
function getGDC (a, b) {
 while (b != 0) {
  var r = a%b;
  a = b;
  b = r;
 }
 return a;
}

 

 

소수

function isPrime(num) {
    if (num === 1) return false;
    for (var i = 2; i <= Math.sqrt(num); i++) {
        if (num % i == 0) return false;
    }
    return true;
}

 

에라토스테네스의 체

function solution(n) {
    const arr = [];
    
    // 인덱스 번호가 주어진 숫자 n과 대응하도록 
		// 빈 배열을 만들고 원소는 true 값으로 채워준다.
  	// 여기서 true 는 소수라는 의미이다.
		// 배열은 0부터 시작하므로, 주어진 숫자 n에 1을 더해준다.
    for (let i = 0; i < n + 1; i += 1) {
        arr.push(true);
    }
    
    // 주어진 수의 제곱근까지만 계산해서 불필요한 반복을 최소화한다.
    // arr[i] 가 소수일 경우, 반복문을 진행한다.
    // 맨 처음 시작하는 2는 소수이므로,
    // 2를 제외한 2의 제곱부터, 제곱 값만 체크하여 지워나간다.
  	// 제곱근까지 반복한다.
    for (let i = 2; i * i <= n; i += 1) {
        if (arr[i]) {
            for (let j = i * i; j <= n; j += i) {
                arr[j] = false;
            }
        }
    }
    
  	// 0과 1은 소수가 아니므로 false 값으로 바꿔준다.
    arr.splice(0, 2, false, false);
    
  	// 배열에서 true인 값만 걸러내고, true인 값의 개수를 출력한다.
    const result = arr.filter((value) => {
        return value !== false;
    })
    
    return result.length;
}

 

 

/