[문제]

Given an array of positive or negative integers

I= [i1,..,in]

you have to produce a sorted array P of the form

[ [p, sum of all ij of I for which p is a prime factor (p positive) of ij] ...]

P will be sorted by increasing order of the prime numbers. The final result has to be given as a string in Java, C#, C, C++ and as an array of arrays in other languages.

Example:

I = [12, 15]; //result = [[2, 12], [3, 27], [5, 15]][2, 3, 5] is the list of all prime factors of the elements of I, hence the result.

Notes:

• It can happen that a sum is 0 if some numbers are negative!

Example: I = [15, 30, -45] 5 divides 15, 30 and (-45) so 5 appears in the result, the sum of the numbers for which 5 is a factor is 0 so we have [5, 0] in the result amongst others.

• In Fortran - as in any other language - the returned string is not permitted to contain any redundant trailing whitespace: you can use dynamically allocated character strings.

(요약) 주어진 배열 각 요소들의 약수 중 소수들을 찾고, 그 약수를 갖는 수만 배열 요소에서 더함. 그리고 [소수, 배열 요소 합]을 배열에 담아서 return.

[풀이]

function sumOfDivided(lst) {
  const primes = [];		// 소수인 약수들을 담을 배열
  const maxNum = Math.max(...lst.map(n => Math.abs(n)));		// 주어진 배열중 가장 큰 수
  const primeList = getPrimes(maxNum);		// 가장 큰 수보다 작거나 같은 소수가 담긴 배열
  // 각 요소들이 어떤 소수인 약수를 갖고 있는지
  const primesOfLst = lst.map(n => {
    const tempArr = [n];

    for(let i = 2; i <= Math.abs(n); i++) {
      if(!(n % i) && primeList.includes(i)) {
        !primes.includes(i) && primes.push(i);
        tempArr.push(i);
      }
    }
 
    return tempArr;
  })

  primes.sort((a, b) => a - b);

  // 소수인 약수를 갖는 배열 요소들의 합
  return primes.map(n => {
    let acc = 0;

    primesOfLst.forEach(arr => {
      if(arr.includes(n)) acc += arr[0];
    })

    return [n, acc];
  })
}

// n보다 작거나 같은 소수 구하는 함수
function getPrimes(n) {
  const numArr = [2];
  let index = 1;

  for(let i = 3; i <= n; i += 2) {
    numArr.push(i);
  }

  while(numArr[index] * numArr[index] <= n) {
    let increase = 0;
    if(!numArr[index]) {
      index++;
      continue;
    }
    else {
      increase = numArr[index];
    }

    for(let i = index + increase; i < numArr.length; i += increase) {
      numArr[i] = 0;
    }

    index++;
  }

  return numArr.filter(num => num !== 0);
}

숫자 n보다 작거나 같은 소수를 찾는 함수 getPrimes를 이용해 주어진 배열 중 가장 큰 수(음수면 양수화)까지의 소수들을 찾음.

주어진 배열들을 순회하는데 그 수가 약수이면서 소수이면 소수인 약수만 담는 배열 primes에 push하고, 각 요소들이 어떤 소수인 약수를 갖고있는지도 따로 return.

그 후에 primes를 오름차순 정렬을 하고, map을 이용해 각 소수가 주어진 배열 요소의 약수인 수일 경우에만 누적 합을 구해서 [소수, 배열 요소 중 소수를 약수로 갖는 수들의 합]을 만들어서 return함.

그렇게 만들어진 배열을 최종적으로 return.