기본 수학 2


1978번 (소수 찾기)

const fs = require("fs");
const input = fs.readFileSync("./input.txt").toString().trim().split('\n');
const inputNums = input[1].trim().split(' ').map(Number);
let count = 0;
let primeNum = 0;
for (let i = 0; i < parseInt(input[0]); i++) {
count = 0;
for (let j = 1; j <= inputNums[i]; j++) {
if (inputNums[i]%j == 0) {
count++;
}
}
if (count == 2) {
primeNum++;
}
}
console.log(primeNum);
  • 소수는 1보다 큰 자연수 중 1과 자기자신만을 약수로 가지는 수이다.
  • 바깥 for문은 주어진 모든 숫자를 연산하도록 한다.
  • 안쪽 for문은 1부터 자기 자신까지 나머지가 0인 숫자를 기록하였다.
  • 여기서 나머지가 0인 숫자가 2개이면 소수인 것으로, primeNum을 1 증가시켰다.
  • primeNum을 출력하였다.
  • 2581번 (소수)

    const fs = require("fs");
    const input = fs.readFileSync("./input.txt").toString().trim().split('\n');
    const min = parseInt(input[0]);
    const max = parseInt(input[1]);
    let count = 0;
    let primeArr = [];
    for (let i = min; i <= max; i++) {
    count = 0;
    for (let j = 1; j <= i; j++) {
    if (i%j == 0) {
    count++;
    }
    if (count > 2) {
    break;
    }
    }
    if (count == 2) {
    primeArr.push(i);
    }
    }
    const primeSum = primeArr.reduce((prev, cur) => prev + cur, 0);
    const primeMin = Math.min(...primeArr);
    if (primeArr.length == 0) {
    console.log(-1);
    } else {
    console.log(primeSum);
    console.log(primeMin);
    }
  • 1978번 문제와 마찬가지로 이중 for문을 통해 소수인지 확인하였다.
  • 바깥쪽 for문은 min이상 max이하의 숫자들을 한번씩 연산하도록 하고,
  • 안쪽 for문은 1부터 해당 숫자까지의 숫자로 나누어 나머지가 0이면 카운트한다.
  • 카운트가 2보다 커지면 소수가 아니므로 멈춘다.
  • 만약 카운트가 2이면 그 숫자는 소수이므로 primeArr에 push한다.
  • 만약 primeArr가 비었으면 그 length가 0이므로 이 경우 -1을 출력한다.
  • 아닌 경우 primeSum과 primeMin을 출력한다.
  • 11653번 (소인수분해)

    const fs = require("fs");
    const input = fs.readFileSync("./input.txt").toString().trim();
    let inputNum = parseInt(input);
    let factoArr = [];
    let count = 2;
    let primeCount = 0;
    let isItPrime = false;
    while (!isItPrime) {
    if (inputNum == 1) {
    break;
    }
    primeCount = 0;
    for (let i = 1; i <= inputNum; i++) {
    if (inputNum % i == 0) {
    primeCount++;
    }
    if (primeCount > 2) {
    break;
    }
    }
    if (primeCount == 2) {
    factoArr.push(inputNum);
    isItPrime = true;
    break;
    }
    if (inputNum % count == 0) {
    factoArr.push(count);
    inputNum = inputNum / count;
    count = 1;
    }
    count++;
    }
    factoArr.sort(function(a, b) {
    return a - b;
    });
    if (inputNum != 1) {
    for (let i = 0; i < factoArr.length; i++) {
    console.log(factoArr[i]);
    }
    }
  • isItPrime이라는 boolean을 선언하여 false일 동안 while문이 진행된다.
  • factoArr에는 소인수 분해로 생긴 소수들이 담겨있다.
  • 우선 inputNum이 1인 경우 아무것도 출력하지 않아야 하므로 이 경우 break해준다.
  • primeCount는 해당 숫자가 이미 소수인지 확인하는 용도로, primeCount가 2이면 해당 숫자는 소수이고 factoArr에 push된다. 또한 isItPrime은 true가 되고 while문은 break 된다.
  • 소수가 아니라면 count를 1씩 증가시켜주면서 inputNum을 count로 나눈 나머지가 0인 count를 찾는다.
  • inputNum을 count로 나눈 나머지가 0이면 inputNum은 count로 나누어주고 count는 factoArr에 push해준다.
  • count = 1로 돌려주어 다시 2부터 검색하도록 한다.
  • factoArr를 오름차순으로 정렬한다.
  • 만약 inputNum이 1이 아니라면 factoArr의 요소들을 하나씩 출력해준다.
  • 1929번 (소수 구하기)

    const fs = require("fs");
    const input = fs.readFileSync("./input.txt").toString().trim().split(" ");
    const min = parseInt(input[0]);
    const max = parseInt(input[1]);
    let isPrimeArr = new Array(max + 1);
    isPrimeArr.fill(true);
    isPrimeArr[0] = false;
    isPrimeArr[1] = false;
    for (let i = 2; i <= max; i++) {
    if (isPrimeArr[i]) {
    for (let j = i + i; j <= max; j += i) {
    isPrimeArr[j] = false;
    }
    }
    }
    for (let i = min; i <= max; i++) {
    if (isPrimeArr[i]) {
    console.log(i);
    }
    }
  • 처음에는 2581번과 같이 2부터 자기 자신에 해당하는 모든 수를 나누어 나머지가 0인 수의 갯수로 문제를 해결하려 하였으나 시간초과가 되었다.
  • 검색해보니 ‘에라토스테네스의 체’라는 알고리즘이 존재했고, 이 알고리즘으로 해결했다.
  • 우선 max+1의 길이의 배열을 선언하고 true로 채워주었다.
  • 0과 1은 소수가 아니므로 값을 false로 하였다.
  • 이중 for문을 선언하였다.
  • 마지막으로 isPrimeArr의 true인 값들을 for문을 통해 출력하였다.
  • 4948번 (베르트랑 공준)

    const fs = require("fs");
    const input = fs.readFileSync("./input.txt").toString().trim().split("\n");
    let count = 0;
    for (let k = 0; k < input.length-1; k++) {
    let n = parseInt(input[k]);
    let isPrimeArr = new Array(2 * n + 1);
    isPrimeArr.fill(true);
    isPrimeArr[0] = false;
    isPrimeArr[1] = false;
    for (let i = 2; i <= 2*n; i++) {
    if (isPrimeArr[i]) {
    for (let j = i + i; j <= 2*n; j += i) {
    isPrimeArr[j] = false;
    }
    }
    }
    isPrimeArr = isPrimeArr.slice(n+1, 2*n+1)
    count = isPrimeArr.reduce((cnt, element) => cnt + (true === element), 0);
    console.log(count);
    }
  • 3중 for문이 되었다.
  • input의 맨 마지막 인덱스 값은 0이므로, 1번째 for문에서 k는 input의 길이-1 미만까지 증가한다.
  • k번째 인덱스 값을 n으로 받고 2*n+1 길이의 isPrimeArr 배열을 선언한다.
  • 1929번과 같이 에라토스테네스의 채 알고리즘으로 소수인지 아닌지를 true/false로 저장한다.
  • isPrimeArr를 slice 메소드를 이용하여 n초과 2*n이하의 숫자들만 남도록 한다.
  • count는 reduce 메소드로 해당 요소가 true이면 1 증가하도록 하여 계산한다.
  • count를 출력한다.
  • 이로써 가장 바깥 for문이 종료되고 k가 1 증가하며 다음 n에 대한 연산도 수행한다.
  • 9020번 (골드바흐의 추측)

    const fs = require("fs");
    const input = fs.readFileSync("./input.txt").toString().trim().split("\n");
    let n = 0;
    let primeNums = [];
    let partition = [];
    for (let k = 1; k < input.length; k++) { // 모든 케이스에 대하여 (1번째 for문)
    partition = [];
    primeNums = [];
    n = parseInt(input[k]);
    let isPrimeArr = new Array(n + 1);
    isPrimeArr.fill(true);
    isPrimeArr[0] = false;
    isPrimeArr[1] = false;
    for (let i = 2; i <= n; i++) { // 2번째 for문
    if (isPrimeArr[i]) {
    for (let j = i + i; j <= n; j += i) { // 3번째 for문
    isPrimeArr[j] = false;
    }
    }
    }
    for (let i = 0; i < isPrimeArr.length; i++) { // 4번째 for문
    if(isPrimeArr[i]) {
    primeNums.push(i); // 우선 1929번과 같은 알고리즘으로 소수를 구하여 배열에 push
    }
    }
    for (let i = 0; i < primeNums.length; i++) { // 5번째 for문
    if (primeNums.includes(n-primeNums[i])) {
    partition.push([n-primeNums[i], primeNums[i], n-primeNums[i]*2]);
    }
    }
    while (partition[i][2] > 0) { // while문
    partition.shift();
    }
    console.log(partition[0][0] + ' ' + partition[0][1]);
    }
  • 어찌저찌 풀어서 맞추긴 했지만 내가 봤을 때도 좋은 코드는 아니다 (…)
  • 구글링해보니 이 문제는 다른사람들도 다들 코드가 길긴 하다. 그래도 더 깔끔하게 풀 수 있도록 노력해야겠다.
  • 4번째 for문 까지는 1929번, 4989번과 같다.
  • 5번째 for문에서는 원래 숫자인 n에서 소수들을 차례로 빼면서 뺀 값이 소수이면(primeNums에 포함되어 있으면) partiton 배열에 [n-소수, 소수, 그 둘의 차]를 push 한다. 이렇게 되면 그 둘의 차가 0보다 클 경우 앞의 숫자가 큰 것이 된다.
  • while문에서는 문제에서 제시한대로 partition안의 요소 배열의 앞 숫자가 작거나 같기 위하여 그 둘의 차가 0보다 클 경우 shift()로 이를 삭제한다.
  • 이렇게 되면 partiton의 0번 인덱스에 정답에 해당하는 두 수가 오게된다. (둘의 차가 0보다 큰 것은 모두 삭제하였으므로 둘의 차가 0인 것부터 내림차순으로 정렬되어 있음) 따라서 위와 같이 출력한다.