Meilleure solution pour trouver des nombres avec exactement 3 diviseurs
J'étudiais de la programmation et j'ai trouvé un exercice pour écrire un algorithme trouvant des "nombres à trois" (nombres qui sont divisibles par exactement 3 Nombres). J'ai écrit ceci:
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++;
}
}
Le problème est qu'il fonctionne un peu lentement et je me demandais si cela pouvait être fait plus rapidement. Est-ce que quelqu'un connaît une solution plus optimisée? Je veux qu'il trouve n numéros de trio consécutifs.
4 réponses
Les seuls nombres à trois sont des carrés de nombres premiers (diviseurs 1, p, p^2). Il suffit de faire Erathostenes et retourner les carrés.
Preuve: Si il a un nombre impair de diviseurs il est connu pour être un carré. Puisque 1 et n^2 sont toujours des diviseurs de n^2, nous ne pouvons avoir qu'un diviseur de plus, c'est-à-dire N. tout diviseur de n serait un autre diviseur de n^2, donc n est premier.
Exemple (basé sur un code donné):
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++;
}
}
Vous pouvez implémenter un algorithme basé sur le tamis D'Eratosthène . Le seul changement est que vous ne marquez pas les multiples de nombres premiers trouvés, mais les multiples de nombres trouvés qui ont au moins 3 diviseurs. La raison en est que vous pouvez être sûr que les multiples de ces nombres ont plus de 3 diviseurs.
EDIT: la solution de Hermann est la meilleure pour les "trios". Mon idée est plus générale et applicable pour "N-somes".
Une solution plus optimisée consiste à trouver les premiers N nombres premiers et à les carré. L'idée derrière cela est que les nombres premiers sont divisibles par seulement deux nombres. Ainsi, les nombres divisibles par seulement trois nombres ont un diviseur supplémentaire qui doit être sa racine carrée. Il doit être un premier afin qu'il n'ajoute pas de diviseur supplémentaire aux diviseurs de nombres principaux.
function threesomeNumber(N){
return firstPrimes(N).map(function(x){return x*x})
}
Où firstPrimes est une fonction qui renvoie les premiers nombres premiers N.
Voici un simple:
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++;
// Stop trying if more that 3 Divisions are Found
if(numberOfDivisions > 3)
break;
}
if(numberOfDivisions === 3)
{
found++;
console.log(found + " = " + i);
}
numberOfDivisions = 1;
i++;
}
}