[Coodility][SieveofEristotheres]ではテストステロンのふるいを用いて少数の

18159 ワード
codility Algorithms テキストリンク

質問する


は、1からNまでの少数の数を返します.

ぶんせき


エラトステネスのふるいテクノロジーの使用が最も速い.

コード#コード#

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;

}
  • ここにはもっと最適化する方法があるに違いないが、私は本当に知らない......

    • sqrtのパラメータをチェック(リンク)

    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]の値を加算するかどうかをチェック
  • すごい...

    • セミ素数(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素数を頭でチェックしていましたが、どの数が他の素数に分かれているかは、その素数を保存して分けてチェックする方が効率的でした.
  • x=私はずっと楽譜を使いたいと思っています.x*y=...よくわからないようです
    • ニフティクラウド mobile backendのUnity SDKを使い倒してみる-NCMBUser編-
    機械学習のカタログモジュラ合成への利用—パートI