50. 소수 만들기 javascript

https://programmers.co.kr/learn/courses/30/lessons/12977

코딩테스트 연습 - 소수 만들기

 

1.이해

주어진 숫자 중 3개의 수를 더해라

소수가 되는 경우의 개수를 구해라

 

2.계획

소수는 1과 자기자신만으로 나누어떨어진다.

모든 배수를 제거하고 남은 수가 소수다.

n까지의 배수를 구하려면 n의 제곱근 이하의 수의

모든 배수를 제거하면 된다.

2-1. 배열 내 소수 찾고 소수 몇갠지 1은 소수가 아니다

2-2. nums에 있는 3개의 숫자 더하는 함수를 만든다.

2-3. 위에서 나온 수들을 빈 배열 안에 담는다.

2-4. 소수 만드는 함수를 사용해서 소수를 찾아서 빈 배열에 담는다.

2-5. 이 배열의 길이를 구한다.

특정 숫자(n)이 소수인지 알기위해선 2부터 n -1 까지 나눴을때 나뉘는지 보면 됨

2부터 n의 제곱근을 한 수만큼만 나눠봐도 된다

 

const findPrime = (numbers) => {
    let primeCount = 0;
  for (i = 0; i < numbers.length; i++) {
    let isNotPrime = false;
      for (j = 2; j <= Math.floor(Math.sqrt(numbers[i])); j++) {
        if (numbers[i] % j === 0) {
          isNotPrime = true;
        } 
      }
    if (isNotPrime === false) {
      primeCount += 1;
    }
    }
    return primeCount;
};

function solution(nums) {
    let numbers = [];

  for (i = 0; i < nums.length; i++) {
    for (j = i+1; j < nums.length; j++) {
      for (k = j+1; k < nums.length; k++) {
        numbers = [...numbers,nums[i] + nums[j] + nums[k]];
      }
    }
  }
  return findPrime(numbers);
};

우선, 배열 내에서 숫자 세개를 임의로 더해서 새로운 배열을 리턴하는 함수를 만들었다.

for 반복문을 세번 돌았는데,, 

배열 내 요소들 세개를 더해야하기 때문,,

function solution(nums) {

let numbers = [];

for (i = 0; i < nums.length; i++) {

for (j = i+1; j < nums.length; j++) {

for (k = j+1; k < nums.length; k++) {

numbers = [...numbers,nums[i] + nums[j] + nums[k]];

}

}

}

return findPrime(numbers);

};

펼침 연산자를 사용하니까 새로 만든 숫자를 배열에 넣기가 수월했다.

 

이제 이 배열을 가지고 또 for 반복문을 해줬다..

숫자를 2부터 해당 숫자 크기까지 나눠봤을때 나눠지면 소수가 아님

근데 숫자를 다 돌기에는 너무 크니까 

숫자를 제곱근해준다.

예를들어, 숫자 20이 있으면 20의 제곱근 4,xxx 이걸 일단 내림해서 4으로 만들고
2부터3까지 나눠지는 숫자가 있는지 확인
4는 2로 나눠지니까 소수 탈락

for (i = 0; i < numbers.length; i++) {

let isNotPrime = false;

for (j = 2; j <= Math.floor(Math.sqrt(numbers[i])); j++)

 

이렇게 소수인지 아닌지 판별해서 소수면 primeCount에 1을 더해줬다.

if (numbers[i] % j === 0) {

isNotPrime = true;

}

}

if (isNotPrime === false) {

primeCount += 1;

}

}

그리고 return primeCount해주면 된다.