素数
エラトステネスの篩による素数生成
√n素数テーブルを用いた素数判定
素因数分解
約数の個数
約数の一覧
code:Prime.js
class Prime {
/* 初期化と素数テーブル生成 */
constructor(n) {
if (n == null) { n = 1e6; }
const primeTable = ...((new Array(n)).keys());
primeTable0 = false;
primeTable1 = false;
let max = Math.sqrt(n);
for(let i = 2;i <= max;++i) {
if (primeTablei !== i) continue;
for (let j = i * i; j < n; j += i) {
if (primeTablej !== j) continue;
primeTablej = i;
}
}
this.size = n;
this.primeTable = primeTable;
this.primeList = primeTable.filter((e,i) => e === i);
}
/* テーブルに生成した素数の2乗までの素数判定 */
isPrime(n) {
if (n < this.size) return this.primeTablen === n;
let max = Math.sqrt(n);
for (let i = 0; this.primeListi <= max; ++i) {
if (n % this.primeListi === 0) return false;
}
return true;
}
/* 最小の素因数 */
getMinimumFactor(n) {
if (n < this.size) return this.primeTablen;
let max = Math.sqrt(n);
for (let i = 0; this.primeListi <= max; ++i) {
if (n % this.primeListi === 0) return this.primeListi;
}
return n;
}
/* 素因数の取得
* 上限: テーブルサイズの二乗*/
getFactor(n) {
const ret = [];
let k = n;
while(!this.isPrime(k)) {
const p = this.getMinimumFactor(k)
ret.push(p);
k /= p;
}
ret.push(k);
return ret;
}
/* 素因数テーブル
* 上限: テーブルサイズ*/
getFactorTable(n) {
const factor = this.getFactor(n);
const maxFactor = factorfactor.length - 1;
const ret = [];
for (let i = 0;this.primeListi <= maxFactor; ++i) {
ret[this.primeListi] = 0;
}
for (const e of factor) { ++rete; }
return ret;
}
/* 約数の個数 */
getDivisorCount(n) {
const factor = this.getFactor(n);
let count = 1;
let prev = factor0;
let factorCount = [];
for (let i = 1; i < factor.length; ++i) {
if (factori != prev) {
factorCount.push(count);
count = 1;
}
else {
++count;
}
prev = factori;
}
factorCount.push(count);
return factorCount.reduce((a,b)=>a * (b+1),1);
}
/* 約数の一覧の取得(未ソート) O(√n)*/
static getDivisors(n) {
let max = Math.sqrt(n);
let ret = [];
if (n % max === 0) {ret.push(max);}
for(let i = 0; i < max; ++i) {
if (n % i == 0) {
ret.push(i);
ret.push(n / i);
}
}
return ret;
}
}
サンプル
ABC112 D - Partition