[31번][중급] 소수 찾기

프로그래머스

이제는 "문제"라고 타이틀도 적을 여유가 없어졌다고 합리화 하고 있지만.. 사실 귀찮아서 그만 적는다ㅋㅋ

 

 

풀이

* 소수 찾기
 * 2 ~ n 중 소수 찾아 반환하기 (1과 자기 자신으로만 나눠지는 숫자)
 * 로직 : 2 ~ n 사이의 각 값에 대해 2 ~ 제곱근 값 사이의 숫자로 나눴을 때, 나머지가 0이라면, prime이 아님 -> 낮으 자리 수 부터 검증을 시작해서 prime arr에 넣어주며 진행 -> prime arr에 있는 숫자로 검증을 하면 효율성이 높아질 것 같음

[pseudo code]
1. prime =[]을 생성
2. while (num <= n)를 생성
    isPrime()함수를 생성
    1) prime 배열을 도는 for loop 생성
        - num % prim[i] == 0 이면 num은 소수가 아니므로, 루프 탈출
        - 끝까지 다 돌았다면, 소수일 가능성이 있으므로, 다음 검증
    2) prime[prime.length-1] + 1부터 num-1까지 도는 루프 생성 => 이 부분은 사실 2를 판별하기 위해서만 필요하다... 간단 버전보다 느린 원인...! 만약 이 부분을 제거하고, 디폴트로 prime = [2], num =3부터 시작한다면? (exited with code=0 in 10.708 seconds 약깐 빨리 됐지만, 별 차이 없음ㅠㅠ 아마도 isPrime 함수 내에서 prime 배열의 값을 도는데 time complexity가 O(n)이기 때문인 것으로 추정된다...ㅋ)
        - num % i == 0이라면, num은 소수가 아니므로, num++하고 루프를 탈출
        - 끝까지 다 돌았다면, 소수이므로 prime 배열에 추가

 

//하면 된다... 삽질의 결과물...ㅋㅋㅋ
function solution(n) {
  let prime = [];
  let num = 2;

  while (num <= n) {
    if (isPrime(num)) {
      prime.push(num);
    }
    num++;
  }

  function isPrime(num) {
    //prime 배열을 돌면서 검사
    for (let i of prime) {
      if (num % i === 0) return false;
    }
    //prime 배열 이외의 숫자를 돌면서 검사
    for (let i = prime[prime.length - 1] + 1; i < num; i++) {
      if (num % i === 0) return false;
    }
    return true;
  }

  return prime.length;
}

console.log(solution(1000000)); // exited with code=0 in 11.828 seconds​

 

[간단 구현 버전]

1. 소수를 받을 빈 배열을 생성
2. 2 ~ num을 도는 루프 생성
   
   1. 숫자가 소수인지 판별해주는 isPrime(num) 함수 생성
   2. 2 ~ 전달 받은 num 값의 제곱근까지 도는 루프 생성
      1. 루프 안에서 num % i가 0이 나오면 false 를 리턴 / 루프가 끝나면 true를 리턴
3. 루프 안에서 isPrime(num)을 호출하고, true를 반환하면 num 값을 소수 배열에 푸쉬
4. prime 배열의 길이를 반환

 

function countPrime(n) {
  let prime = [];
  for (num = 2; num <= n; num++) {
    if (isPrime(num)) prime.push(num);
  }
  return prime.length;
}

function isPrime(num) {
  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (num % i === 0) return false;
  }
  return true;
}

console.log(countPrime(1000000)); // exited with code=0 in 0.455 seconds

 

=> 확실히 제곱근까지만 검증을 진행하기 때문에, O(n) 중 n의 길이가 짧아져서 숫자가 커질수록 유리하다.