Meilleure solution pour trouver des nombres ayant exactement 3 diviseurs

Question

J'étudiais la programmation et j'ai trouvé un exercice consistant à écrire un algorithme permettant de trouver les "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 assez lentement et je me demandais s'il pouvait être fait plus rapidement. Quelqu'un connaît-il une solution plus optimisée ? Je veux qu'il trouve N nombres consécutifs à trois.

Answer 1

Les seuls nombres à trois sont des carrés de nombres premiers (diviseurs 1, p, p^2). Il suffit de faire Erathostenes et de retourner les carrés.

Preuve : S'il a un nombre impair de diviseurs, on sait que c'est 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 le 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++;
  }
}

Answer 2

Vous pourriez implémenter un algorithme basé sur le tamis d'Eratosthène . Le seul changement est que vous ne marquez pas les multiples des nombres premiers trouvés, mais les multiples des 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 les "N-somes".

Answer 3

Une solution plus optimisée consiste à trouver la première N Les nombres premiers et les carrés. L'idée derrière cela est que les nombres premiers sont divisibles par seulement deux nombres. Donc les nombres divisibles par seulement trois nombres ont un diviseur supplémentaire qui doit être leur racine carrée. Il doit s'agir d'un nombre premier pour ne pas ajouter de diviseur supplémentaire aux diviseurs du nombre principal.

function threesomeNumber(N){
    return firstPrimes(N).map(function(x){return x*x})
}

Où firstPrimes est une fonction qui renvoie le premier N primes.

Answer 4

En voici une 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++;
    }
}

Answer 5

En voici une dont la complexité temporelle est de O(N^(1/2)*N^(1/4)).

    public int exactly3Divisors(int N)
    {
        int count=0,flag=0;
        for(int i=2;i*i<=N;i++){
            for(int j=2;j*j<=i;j++){
                if(i%j==0){
                    flag=1;
                    break;
                }
            }
            if(flag==0){
                count++;
            }
            flag=0;
        }
        return count;
    }