私はいくつかのプログラミングを研究していて、「3つの数」(正確に3つの数で割り切れる数)を見つけるアルゴリズムを書く練習を見つけました。私はこれを書いた:
function threesomeNumber(N) {
var found = 0;
var i = 1;
var numberOfDivisions = 1;
while (found < N) {
for (var j = 2; j <= i; j++) {
if (i % j === 0) {
numberOfDivisions++;
}
}
if (numberOfDivisions === 3) {
found++;
console.log(found + " = " + i);
}
numberOfDivisions = 1;
i++;
}
}
問題は、それが少し遅いので、もっと早くできるのかと思っていました。より最適化されたソリューションを知っている人はいますか?N個の連続した3人組の数字を見つけて欲しい。
唯一の3つの数は、素数の2乗です(除数1、p、p ^ 2)。Erathostenesを実行し、正方形を返します。
証明:奇数の除数がある場合、正方形であることが知られています。1とn ^ 2は常にn ^ 2の約数であるため、除数はもう1つしかありません。ien nの約数はn ^ 2の別の約数になるため、nは素数です。
例(与えられたコードに基づく):
function threesomeNumber(N) {
var found = 0;
var i = 2;
var prime = true;
while (found < N) {
// Naive prime test, highly inefficient
for (var j = 2; j*j <= i; j++) {
if (i % j === 0) {
prime = false;
}
}
if (prime) {
found++;
console.log(found + " = " + (i*i));
}
prime = true;
i++;
}
}
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加