소수 Prime

Ramne·2021년 8월 7일

알고리즘 풀이

목록 보기

1/4

소수

1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수
따라서 2를 제외한 짝수는 소수가 될 수 없으며,
홀수 중에서도 제곱근으로 나누어 떨어지는 것 또한 제외된다.

🔥 에라토스테네스의 체 공부하기!!

isPrime

문제
1 이상의 자연수를 입력받아 소수(prime number)인지 여부를 리턴해야 합니다.
입력
인자 1 : num
number 타입의 수
출력
boolean 타입을 리턴해야 합니다.
입출력 예시
let output = isPrime(2);
console.log(output); // --> true
output = isPrime(6);
console.log(output); // --> false
output = isPrime(17);
console.log(output); // --> true

function isPrime(num) {
  if (num === 2) return true; // 짝수 중 2만 유일하게 예외니까
  if (num === 1 || !(num % 2)) return false; 

  let squareRoot = Math.sqrt(num)
  for (let i = 3; i <= squareRoot; i += 2) {
    if (!(num % i)) return false;
  }
  return true;
}

listPrimes

문제
2 이상의 자연수를 입력받아 2부터 해당 수까지의 소수들을 리턴해야 합니다.
입력
인자 : num
number 타입의 정수 (num >= 2)
출력
string 타입을 리턴해야 합니다.
2-3-5-7의 형식으로 리턴해야 합니다.
주의 사항
이중 반복문(double for loop)을 사용해야 합니다.
입출력 예시
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'

function listPrimes(num) {
 
    let result = '2' 
    // 짝수 중 유일하게 소수인 2
    // num은 최소 '2'를 포함한 결과값을 리턴
    
    for (let i = 3; i <= num; i += 2) { 
    // num까지의 수 중 홀수만 i로 선별
    
    let sqrt = Math.sqrt(i) 
    let isPrime = true; // 소수 판별의 조건 기본 설정

      for (let j = 3; j <= sqrt; j += 2) { 
      // 홀수 i 중 소수 j 판별
        if(!(i % j)) {
          isPrime = false; // 제곱근으로 나누어 떨어지면 소수가 아니다.
          break; // 안쪽 for문 해제. 
          // continue도 가능하지만 j문을 한번 더 도는 낭비가 발생
        }
      }
      
      if(isPrime) result = `${result}-${i}`;
      // 안쪽 for문을 거쳐 떨어지는 홀수 i가 소수인지 판별하기 위해 꼭 필요한 조건문
      // 제곱근으로 나눠지지 않는 경우만 담는다.
    }
    return result;
}

TIL

break vs continue
break 더 반복하지 말고, 바로 반복문을 끝내라
continue 현재는 건너 뛰고, 다음 반복으로 넘어가라

primePassword (BFS)

문제
다음의 조건을 만족하면서 현재의 비밀번호('curPwd')를 새 비밀번호(newPwd)로 변경하는 데 필요한 최소 동작의 수를 리턴해야 합니다.

한 번에 한 개의 숫자만 변경가능하다.

4자리의 소수(prime)인 비밀번호로만 변경가능하다.

정리하면, 비밀번호가 계속 소수를 유지하도록 숫자 한 개씩을 바꿔갈 때
현재 비밀번호에서 새 비밀번호로 바꾸는 데 최소 몇 개의 숫자를 변경해야 하는지를 리턴해야 합니다.
입력
인자 1 : curPwd
number 타입의 1,000 이상 9,999 이하의 자연수
인자 2 : newPwd
number 타입의 1,000 이상 9,999 이하의 자연수
출력
number 타입을 리턴해야 합니다.
주의사항
4자리인 소수는 1,000 이상의 소수를 말합니다.(0011, 0997 등은 제외)
입출력 예시
let output = primePassword(1033, 1033);
console.log(output); // --> 0
output = primePassword(3733, 8779);
console.log(output); // --> 3 (3733 -> 3739 -> 3779 -> 8779)

접근 방법

현재 비밀번호에서 새 비밀번호로 변경하는 데 필요한 최소 동작의 수
-> BFS와 Q 자료구조를 통해 접근한다.

// 유효성 검사와 비밀번호 구현 파트를 나누고 BFS 접근 방식으로 푼다.
let Q = 비밀번호 리스트
let isUsed = 사용한 비밀번호
while 문을 통해 큐 리스트가 빌 떄까지 반복하는데
  if (현재 비밀번호 === 원하는 새 비밀번호) 탈출!
  for (let i~) {
  if (조건과 유효성 검사 통과한다면)
  Q 리스트에 추가한다.
  }

풀이

// 소수 판별 함수 -> 유효성 검사
const isPrime = (num) => {
  if (!(num % 2)) return false; 
  let sqrt = Math.sqrt(num)
  for (let i = 3; i <= sqrt; i += 2) {
    if (!(num % i)) return false;
  }
  return true;
}

// 비밀번호를 만드는 함수
const primePassword = (curPwd, newPwd) => {
  
  let Q = [[curPwd, 0]]; // 큐에 현재 비밀번호와 변경한 횟수를 함께 넣어준다.
  let isUsed = [curPwd];
  
  while (Q.length) {
    let [now, step] = Q.shift();
    if (now === newPwd) return step;
    for (let i = 0; i < 4; i++) { 
      let digits = String(now).split('').map( el => Number(el)) 
      // 이 위치여야 i값에 따라 초기화가 된다.
      for (let d = 0; d <= 9; d++) { 
        if (digits[i] !== d) { 
          digits[i] = d; 
          let next = Number(digits.join(''))
          if (next === newPwd) return step + 1; 
          // 원하던 값을 찾으면 뒤에 남은 반복 연산을 두고 리턴하라!
          if (next > 1000 && isPrime(next) && !isUsed.includes(next)) {
            Q.push([next, step + 1])
            isUsed.push(next)
          }
        }
      }
    }
  }
};

Ramne

💡