소수 만들기, 소수 찾기

1️⃣ 소수 만들기

📚 문제

문제 설명
주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항
nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.
입출력 예
nums result
[1,2,3,4] 1
[1,2,7,6,4] 4
입출력 예 설명
입출력 예 #1
[1,2,4]를 이용해서 7을 만들 수 있습니다.

입출력 예 #2
[1,2,4]를 이용해서 7을 만들 수 있습니다.
[1,4,6]을 이용해서 11을 만들 수 있습니다.
[2,4,7]을 이용해서 13을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.

💡 풀이

// 소수 여부를 판별하는 함수를 생성한다
// 숫자 3개의 조합의 경우의 수를 3차 반복문을 써서 구한다
// 그 경우의 수의 합이 소수이면 answer를 1씩 더한다
// 반복문이 다 돌면 answer를 리턴한다

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

function solution(nums) {
    let answer = 0;

    for (let i = 0; i < nums.length - 2; i++) {
        for (let m = i + 1; m < nums.length - 1; m++) {
            for (let n = m + 1; n < nums.length; n++) {
                if (prime(nums[i] + nums[m] + nums[n])) {
                    answer++;
                }
            }
        }
    }
    return answer;
}

2️⃣ 소수 찾기

📚 문제

문제 설명
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건
n은 2이상 1000000이하의 자연수입니다.
입출력 예
n result
10 4
5 3
입출력 예 설명
입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

❗️ 첫번째 시도

function isPrime(num) {
    if (num === 2) {
        return true;
    }

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

function solution(n) {
    let answer = 0;
    for (let m = 2; m <= n; m++) {
        if (isPrime(m)) {
            answer++;
        }
    }
    return answer;
}

❗️ 테스트는 다 통과했으나 복잡도에서 막혔다

💡 풀이

function solution(n) {
    // 소수 리스트 담을 배열 생성
    let arr = [];

    // 0과 1을 제외한 2부터 n까지 배열에 담아줍니다.
    for (let i = 2; i <= n; i++) {
        arr[i] = i;
    }

    for (let i = 2; i <= n; i++) {
        // 인덱스 2부터 반복문 돌면서 0이면 다시 다음 반복문을 돕니다.
        if (arr[i] === 0) continue;

        // 각 인덱스(i)의 배수들을 0으로 지정해줍니다.
        for (let j = i * 2; j <= n; j += i) {
            arr[j] = 0;
        }
    }

    // filter를 이용해 0이아닌 수들의 개수를 return합니다.
    return arr.filter((v) => v !== 0).length;
}

✅ 다른 문제에도 자주 나올 정도로 알아둬야 할 문제!
지금은 다른 문제에도 적용할 수 있을 정도로 익숙하지만 처음에는 이 코드를 익히는데 꽤 연습이 필요했다🤔