CodeWars 코딩 문제 2021/03/08 -Goldbach’s Conjecture
[문제]
German mathematician Christian Goldbach (1690-1764) conjectured that every even number greater than 2 can be represented by the sum of two prime numbers. For example, 10 can be represented as 3+7 or 5+5.
Your job is to make the function return a list containing all unique possible representations of n in an increasing order if n is an even integer; if n is odd, return an empty list. Hence, the first addend must always be less than or equal to the second to avoid duplicates.
Constraints : 2 < n < 32000 and n is even
Examples
26 --> ['3+23', '7+19', '13+13']
100 --> ['3+97', '11+89', '17+83', '29+71', '41+59', '47+53']
7 --> []
(요약) 주어진 숫자를 두 소수의 합으로 나타낼 수 있는 모든 경우를 구하라. 왼쪽수가 오른쪽수보다 작아야되고, 주어진 숫자가 홀수면 빈 배열을 return
.
[풀이]
function goldbachPartitions(n){
if(n % 2 === 1) return []; // 주어진 숫자가 홀수면 빈 배열 return
const primes = getPrimes(n);
let answer = '';
primes.forEach((prime, idx, arr) => {
if(!answer.includes(`+${prime},`) && arr.includes(n - prime)) {
answer += `${prime}+${n - prime},`;
}
});
return answer.split(',').filter(str => str.length);
}
// 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+m,
형태로 담는다.
숫자가 사용되었는지 +n,
으로 확인하는 이유는 사용된 숫자는 반드시 뒤쪽에 위치하니까 저렇게 확실하게 찾을 수 있다.
그냥 숫자만 넣으면 겹치는 경우가 생기기도 한다.
그렇게 만들어진 문자열을 마지막에 split(',')
하고, 마지막 요소는 빈 문자열이니 그것만 제거하고 return
하면 된다.
주어진 숫자가 홀수일 때는 처음에 빈 배열을 return
시키면 된다.
Author And Source
이 문제에 관하여(CodeWars 코딩 문제 2021/03/08 -Goldbach’s Conjecture), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@hemtory/CodeWars20210308
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
function goldbachPartitions(n){
if(n % 2 === 1) return []; // 주어진 숫자가 홀수면 빈 배열 return
const primes = getPrimes(n);
let answer = '';
primes.forEach((prime, idx, arr) => {
if(!answer.includes(`+${prime},`) && arr.includes(n - prime)) {
answer += `${prime}+${n - prime},`;
}
});
return answer.split(',').filter(str => str.length);
}
// 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+m,
형태로 담는다.
숫자가 사용되었는지 +n,
으로 확인하는 이유는 사용된 숫자는 반드시 뒤쪽에 위치하니까 저렇게 확실하게 찾을 수 있다.
그냥 숫자만 넣으면 겹치는 경우가 생기기도 한다.
그렇게 만들어진 문자열을 마지막에 split(',')
하고, 마지막 요소는 빈 문자열이니 그것만 제거하고 return
하면 된다.
주어진 숫자가 홀수일 때는 처음에 빈 배열을 return
시키면 된다.
Author And Source
이 문제에 관하여(CodeWars 코딩 문제 2021/03/08 -Goldbach’s Conjecture), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hemtory/CodeWars20210308저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)