Lepsze rozwiązanie do wyszukiwania liczb z dokładnie 3 dzielnikami

Question

Studiowałem programowanie i znalazłem ćwiczenie, aby napisać algorytm znajdujący "liczby trójkątów" (liczby, które są podzielne przez dokładnie 3 liczby). Napisałem to:

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++; 
    } 
} 

Problem polega na tym, że działa on wolno i zastanawiałem się, czy można to zrobić szybciej. Czy ktokolwiek wie o bardziej zoptymalizowanym rozwiązaniu? Chcę, żeby znalazła N kolejnych liczb z trójkami.

Answer 1

Jedynymi liczbami w trójkącie są kwadraty liczb pierwszych (dzielniki 1, p, p^2). Po prostu wykonaj Erathostenes i zwróć kwadraty.

Dowód: Jeśli ma nieparzystą liczbę dzielników, wiadomo, że jest kwadratem. Ponieważ 1 i n^2 są zawsze dzielnikami n^2, możemy mieć tylko jeden dzielnik, tj. N. Każdy dzielnik n byłby kolejnym dzielnikiem n^2, dlatego n jest liczbą pierwszą.

Przykład (na podstawie określonego kodu)

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

Można zastosować algorytm oparty na sieve of Eratosthenes. Jedyną zmianą jest to, że nie zaznaczasz wielokrotności znalezionych liczb pierwszych, ale wielokrotności znalezionych liczb, które mają co najmniej 3 dzielniki. Powodem jest to, że możesz mieć pewność, że wielokrotności tych liczb mają więcej niż 3 dzielniki.

EDYCJA: Rozwiązanie Hermanna jest najlepsze dla "trójkątów". Mój pomysł jest bardziej ogólny i dotyczy "N-somes".

Answer 3

bardziej zoptymalizowanej rozwiązaniem jest znalezienie pierwsze N liczb i kwadratowy ich. Ideą tego jest to, że liczby pierwsze są podzielne przez tylko dwie liczby. Więc liczby podzielne przez tylko trzy liczby mają dodatkowy dzielnik, który musi być pierwiastkiem kwadratowym. Musi być podstawową, więc nie dodaje dodatkowego dzielnika do głównych dzielników liczb.

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

Gdzie firstPrimes to funkcja, która zwraca pierwsze N liczb pierwszych.

Answer 4

Oto prosta:

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++; 
    } 
}