素数メニュー【ゴールドバッハ予想・中国剰余定理・paiza予想】
【ゴールドバッハ予想】コード
reader.on('close', () => {
const N = Number(lines[0]);
// ここから…エラトステネスの篩
const prime = new Array(N + 1).fill(true); // 0 ~ N が素数か否真偽値 (trueで初期化)
[prime[0], prime[1]] = [false, false]; // 0 と 1 は 2以下なので false
for (let i = 2; i * i <= N; i++) {
if (prime[i]) { // true のときのみ実行
for (let j = 2; j * i <= N; j++) {
prime[i * j] = false; // 2つの値の積は素数に該当しないので false
}
}
}
const Prime_number = []; // 0 ~ N の素数を保存するための配列
for (let i = 0; i <= N; i++) {
if (prime[i]) { // prime[i] が true なら
Prime_number.push(i); // i は素数
}
}
// ここまで…エラトステネスの篩
const Prime_pair = [0, N]; // 和 が N になる 素数 の ペア
const n = Prime_number.length;
for (let i = 0; i < n; i++) {
const [a, b] = [Prime_number[i], N - Prime_number[i]];
if (a > b) { // a が b より大きくなれば…
break; // 処理を止める
}
if (Prime_number.includes(b)) { // Prime_number に b が含まれていれば…
const [c, d] = [...Prime_pair]; // c, d に Prime_pair を 展開した値を代入
if (a * b > c * d) { // a × b > c × d の積なら…
[Prime_pair[0], Prime_pair[1]] = [a, b]; // Prime_pair の各値を a, b で上書き
}
}
}
Prime_pair.forEach(p => {
console.log(p);
});
});
足して N となる 2 つの素数のうち 積が最大であるものを小さい順に 2 行で出力。
なので エラトステネスの篩で 0 〜 N に含まれる素数を抽出して その中に含まれる 2つの素数(a >= b)を取出し (a × b)と元の値の積(c × d)を比較しながら Prime_pair の値を更新しています。
【中国剰余定理】コード 1/2
reader.on('close', () => {
const [m1, m2, b1, b2] = lines[0].split(' ').map(Number);
// m1, m2 は 互いに素である正の整数
// [b1, b2] = [Z % m1, Z % m2]
// Z は [0, m1 * m2) に含まれる唯一の整数
const n = m1 * m2;
for (Z = n - 1; Z >= 0; Z--) { // [0, m1 * m2) の範囲を 降順にループ
if (Z % m1 === b1 && Z % m2 === b2) { // Z % m1 が b1 且つ Z % m2 が b2 なら…
console.log(Z);
break;
}
}
});問題文の条件を準えてコーディングすると こんな感じになりました。最初はループを昇順にしていましたが タイムオーバーになったので 降順に書き換えると 時間内にクリアできました。(ｰ｡ｰ)ﾌｩ
【中国剰余定理】コード 2/2
reader.on('close', () => {
const [m1, m2, b1, b2] = lines[0].split(' ').map(Number);
// m1, m2 は 互いに素である正の整数
// [b1, b2] = [Z % m1, Z % m2]
// Z は [0, m1 * m2) に含まれる唯一の整数
for (let i = 0; i < m2; i++) { // ループの範囲は[0, m2)
const z1 = m1 * i + b1; // z1 は [0, m1 * m2) に含まれる b1 = z1 % m1 を満たす整数
if (z1 % m2 === b2) { // z1(b1 = z1 % m1 を満たす整数) % m1 が b2 なら…
const Z = z1; // [b1, b2] = [z1 % m1, z1 % m2]を満たすので Z = z1
console.log(Z);
break;
}
}
});C++の実装例と解説を参照しながら修正すると コード1と比べ 実行速度が上がりました。b1 = z1 % m1 を満たす整数 z1 を求めてから b2 = z1 % m2 を満たすかどうか調べています。(o・。・o)
【paiza予想】コード
let prime = true;
// ゴールドバッハ予想より… 3 より大きな偶数は 2 つの素数の和として表すことができるので…
for (let i = 3; i * i < 10 ** 8; i += 2) { // 3 より大きな 奇数の…
const x = i * i; // 平方数を求めて…
for (let i = 2; i * i <= x - 2; i++) { // 2 ~ x - 2 の平方根までループして…
if ((x - 2) % i === 0) { // x - 2 が i で割り切れれば…(奇数 + 偶数 = 奇数 になるが 偶数の素数は2のみなので…)
prime = false;
console.log(x); // 2 つの素数の和として表すことができない
break;
}
}
}
if (prime) {
console.log('paiza\'s conjecture is correct.');
}
ゴールドバッハ予想より 3 より大きな偶数は 2 つの素数の和として表すことができることがわかっているので 奇数の平方数について調べればOKでした。
偶数 + 偶数 = 偶数, 奇数 + 奇数 = 偶数, 偶数 + 奇数 = 奇数, 偶数の素数は2のみ…
なので N – 2 が素数に該当しない場合は 2つの素数の和として表すことができないことになります。
コメント