[Codility][Sieve of Erastothenes] 에라토스테네스의 체 이용하여 소수찾기

minnsane·2020년 9월 18일
0

문제

1부터 N까지의 수 중에 소수의 갯수를 return

분석

에라토스테네스의 체 기법을 이용하면 가장 빠르다.

코드

const solution = num => {
  let isPrime = new Array(num+1).fill(1).fill(0, 0, 2);
  let sqrt = Math.sqrt(num);

  for(let i=2; i< sqrt; i++){
    let j = i*i;
    while(j<=num){
      isPrime[j] = 0;
      j += i;
    }
  }

  return isPrime.filter(v => v).length - 2;
}

CountNonDivisible

에라토스테네스의 체 방식 (타임아웃)

const solution = arr => {
  let len = arr.length;
  let numbers = new Array(2*len+1).fill(0);

  for(let d of arr){
    let k = d;
    while(k<= 2*len){
      numbers[k]++;
      k += d;
    }
  }
  let answer = [];

  for(let n of arr){
      answer.push(len-numbers[n]);
  }
  
  return answer;

}
  • 분명 뭔가 여기서 더 나아가서 최적화 하는 방법이 있을 것 같은데 도저히 모르겠다...
const solution = arr => {
  let len = arr.length;
  let divisors = new Array(len*2 +1).fill(0);

  for(let n of arr){
    divisors[n]++;
  }

  let answer = [];

  for(let n of arr){
    let sqrt = Math.sqrt(n);
    let count = 0;
    for(let i=1; i<=sqrt; i++){
      if(n%i===0){
        count += divisors[i];
        if(i!==sqrt){
          count += divisors[n/i];
        }
      }
    }
    answer.push(len-count);
  }

  return answer;

}
  • sqrt까지의 인수를 체크하는 방식
  • 해당 인수가 배열에 있는지 없는지 체크하는 방식이 divisors[i]의 값을 더하는것
  • 대단....

semi prime number (prime*prime) 값 찾기

const solution = (N, P, Q) => {
  let prime = new Array(N+1).fill(0);
  let semiPrimeCount = new Array(N+1).fill(0);

  for(let i=2; i<=N; i++){
    let k = i*i;
    while(k<=N){
      if(prime[k]===0){
        prime[k] = i;
      }
      k += i;
    }
  }

  let count = 0;
  for(let i=1; i<=N; i++){
    if(prime[i]){
      let j = i/prime[i];
      if(prime[j]===0) count++;
    }
    semiPrimeCount[i] = count;
  }

  let answer = [];
  
  for(let i=0; i<P.length; i++){
    answer.push(semiPrimeCount[Q[i]]-semiPrimeCount[P[i]-1]);
  }
  
  return answer;
}
  • 나도 처음엔 머리를 쓴다고 prev prime 갯수를 체크하는 배열을 썼었는데, 그것보다 어떤 수가 다른 소수로 나눠진다면 그 소수자체를 저장하고 그걸로 나눠서 체크하는 방식이 훨씬 효율적이다.
  • 나는 뭔가 x = ...로 푸는것만 계속 생각하지, x*y = ... 를 생각을 잘 못하는 것 같다 ㅠ_ㅠ
profile
Knope's not-so-secret binder

0개의 댓글