1. 소수 구하기

1) 소수 판별하기

---

소수(prime)

• 자신의 약수가 1과 자기 자신 2개만 있는 수

• 자신을 1 부터 자기 자신까지 나누었을 때 나머지가 0인 되는(나누어 떨어지는) 수가 1과 자기 자신만 있는 수

• 1은 소수가 아니다.

• 소수는 약수가 1과 자기 자신 2개만 있는 숫자이므로, num을 1부터 num까지의 수로 나누어서 나머지가 0이면(나누어 떨어지면) 그 수는 num의 약수이므로 빈 배열에 담아준다.

• 이후 소수라면 빈 배열에 약수가 2개만 있어야 하므로 약수가 담긴 배열의 길이가 2이면 소수이고 2가 아니면 소수가 아니다.

function isPrime(num) {
  let result = [];

  for (let i = 1; i <= num; i++) {
    if (num % i === 0) {
      result.push(i);
    }
  };

  if (result.length === 2) {
    return true;
  } else {
    return false;
  }
};

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

2) 소수 구하기

---

• 소수는 1과 자기 자신으로만 나누어 떨어져야 하기 때문에 2 부터 자기 자신 이전까지의 수로 나누어 떨어지면 소수가 아니라는 점을 이용하여 소수를 구한다.

• 첫번째 반복문에서 인자로 받은 배열을 돌면서 각 요소를 2 부터 해당 요소보다 1작은 수까지 나누어 본다. 그래서 2 부터 1작은 수까지로 나누어서 1개라도 나누어 떨어진다면 prime을 false로 만들고 건너뛴다.

• 하지만 나누어 떨어지는 수가 1개도 없다면 true 그대로 if문을 통과하게 되므로 아래에서 true인 수들만 배열에 담아준다. 이 배열이 소수만 모아둔 배열이 된다.

function solution(arr) {
    let result = [];

    for (let i = 0; i < arr.length; i++) {
        let prime = true;
        for (let j = 2; j < arr[i]; j++) {
            if (arr[i] % j === 0) {
                prime = false;
                break;
            }
        }
        if (prime) {
            result.push(arr[i]);
        }
    }
    return result;
}

console.log(solution([4, 9, 5, 7, 10, 55, 1, 56, 789]))  // [ 5, 7, 1 ]

2. 소인수 구하기

---

소인수(prime)

• 해당 수의 약수들 중에서 소수인 수

• 소인수는 해당 수의 약수를 먼저 구하고, 그 약수들 중에서 소수인 수만 걸러내는 방식으로 구한다.

• 소수인지 판별하는 prime 변수를 첫 번째 for문 다음에 선언해두는 이유는, if문의 조건을 만족해서 prime이 false로 바뀐 후에 다시 true로 만들어줘야 약수가 담겨 있는 배열의 다음 요소에서 다시 false인지 판별할 수 있기 때문이다.

• true를 for문 밖에 선언해버리면 첫번째 요소에서 false가 나올 경우 이후에도 계속 prime은 false에서 바뀌지 않기 때문이다.

function solution(num) {
    let divisor = [];

    for (let k = 2; k <= num; k++) {  // 1은 소수가 아니기 때문에 약수를 구할 때 먼저 걸러준다.
        if (num % k === 0) {
            divisor.push(k);  // [2, 4, 5, 10, 20]
        }
    }

    let primeFactor = [];

    for (let i = 0; i < divisor.length; i++) {
        let prime = true;  // prime 변수 선언 위치 주의
        for (let j = 2; j < divisor[i]; j++) {
            if (divisor[i] % j === 0) {
                prime = false;
                break;
            }
        }
        if (prime) {
            primeFactor.push(divisor[i]);
        }
    }
    return primeFactor;
}

console.log(solution(20))  // [2, 5]