DAY. 5 반복문 복습

17. isPrime

function isPrime(num) {
 let isNumPrime = true;
  // 1부터 num까지 num(자기 자신)으로 나누어 떨어지는 경우 (나머지가 0인 경우)
  // num은 소수이다
 if(num === 1){
  return false;
 }

 for(let i = 2; i < num; i++){
   if(num% i === 0){
     isNumPrime = false;
   }
 }
 return isNumPrime
}

1부터 자기자신까지 계속해서 나눈다.
%연산자를 이용했는데 나머지가 0이 나온다면 나누어 떨어진다는 것이니
소수가 아니기 때문에 false를 리턴한다.
이 과정에서 살아남은 숫자는 진정한 '소수'이기 때문에 true를 리턴한다.

18. listPrimes

function listPrimes(num) {
let result = '2'
for(let i =3; i <= num; i++) { //3부터 num까지 반복해준다
let isPrime = true
for(let j = 2; j < i; j++) {
if(i % j === 0){
  isPrime = false
  break
  }
 }
  if(isPrime === true){
  result = result + '-' + i
  }
}
return result;
}

//result 변수를 선언해준다. '2'를 할당해준다.
//for문을 만들어준다.i를 선언해주고 3을 할당해준다. i는 num보다 작거나 같다. i++
//3부터 num까지 반복해준다
//isPrime을 선언해주고 true를 할당한다.
//또 for문을 만들어준다. j를 선언해주고 2를 할당해준다. j는 i보다 작다. j는 1씩 증가한다.
//만약 i를 j로 나누었을 때 0으로 나누어떨어진다면
//isPrime은 false이다.
//false라면 break를 걸어서 반복문을 종료하고 다시 바깥의 i for문을 작동시킨다.
//만약 isPrime이 true라면
//result 는 result + '-' + i 이다
//result를 리턴해준다.

입출력예시

let output = listPrimes(2);
console.log(output); // --> '2'

output = listPrimes(6);
console.log(output); // --> '2-3-5'

output = listPrimes(18);
console.log(output); // --> '2-3-5-7-11-13-17'

result값은 result가 2부터 시작하기 때문에 처음엔 2가 나오고 소수값 j가 계속해서 추가된다

변수 primeIs를 재할당할때 let 을 써서 틀렸다 선언은 한번만 하자

소수 판별식 방법 3가지

1. 직접 나누기

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

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

2. n/2 까지 나누어 계산

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

  for(let i = 2; i<=num/2; i++){
    if(num % i === 0){
      return false;
    }
  }
  return true;
}

1번 방법보다 for문을 더 적게 돌릴 수 있다.
num의 약수는 num의 절반을 넘을 수 없기 때문이다.

3. n의 제곱근까지 나누어 계산

function isPrime(num) {
  let result = false;
  if(num === 2)
  return true;

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

num의 제곱근보다 작은 수에서 나누어지는 수가 나오지 않는다면 num의 제곱근보다 큰 수에서 나누어지는 수가 나오지 않는다.
세가지 방법중 가장 빠르게 계산된다.