Trouver le plus grand nombre premier parmi les 600851475143 ?

Question

J'essaie de résoudre le problème 3 de http://projecteuler.net . Cependant, lorsque je lance le programme, rien ne s'imprime. Que dois-je faire de mal ? Problème : Quel est le plus grand facteur premier du nombre 600851475143 ?

public class project_3 
{
    public boolean prime(long x)   // if x is prime return true
    {
        boolean bool = false;

        for(long count=1L; count<x; count++)
        {
            if( x%count==0 )
            {
                bool = false;
                break;
            }
            else { bool = true; }
        }
        return bool;
    }

    public static void main(String[] args)
    {
        long ultprime = 0L;  // largest prime value
        project_3 object = new project_3();

        for(long x=1L; x <= 600851475143L; x++)
        {
            if( object.prime(x)==true )
            {
                ultprime = ((x>ultprime) ? x : ultprime);
            }
        }
        System.out.println(ultprime);
    }
}

Answer 1

Non seulement votre prime la fonction de vérification renvoie toujours false même s'il fonctionnait correctement, votre boucle principale ne cherche pas du tout les facteurs du nombre d'entrée, mais seulement le plus grand nombre premier inférieur ou égal à celui-ci. En pseudo-code, votre code est équivalent à :

foo(n):
    x := 0 ;
    foreach d from 1 to n step 1:
        if is_prime(d):          // always false
            x := d
    return x                     // always 0

is_prime(d):
    not( d % 1 == 0 )            // always false

Mais vous n'avez pas du tout besoin de la fonction de vérification de la prime ici. La fonction suivante trouve tous les facteurs d'un nombre, par Division de première instance :

factors(n):
    fs := []
    d  := 2
    while ( d <= n/d ):
        if ( n % d == 0 ): { n := n/d ; fs := append(fs,d) }
        else:              { d := d+1 }
    if ( n > 1 ): { fs := append(fs, n) }
    return fs

Le test de divisibilité est effectué uniquement jusqu'à la racine carrée du nombre. Chaque facteur, au fur et à mesure qu'il est trouvé, est divisé à partir du nombre à factoriser, ce qui réduit encore le temps d'exécution. La factorisation du nombre en question s'exécute instantanément, ne nécessitant que 1473 itérations.

Par construction, tous les facteurs ainsi trouvés sont garanti pour être premier (c'est pourquoi aucune vérification du caractère premier n'est nécessaire). Il est crucial d'énumérer les diviseurs possibles en ordre ascendant pour que cela se produise 1 . L'ordre ascendant est également le plus efficace car un nombre donné a plus de chances d'avoir un facteur premier plus petit qu'un plus grand. L'énumération des primes au lieu de cotes, bien que cela ne soit pas nécessaire, sera plus efficace si vous avez un moyen efficace d'obtenir ces nombres premiers, pour tester la division par.

Il est trivial d'augmenter ce qui précède pour trouver le le plus grand facteur : il suffit de mettre en œuvre append comme

append(fs,d):
    return d

---

1 car alors, pour tout diviseur composite d du nombre original à factoriser, quand nous atteindrons d nous aurons déjà divisé ses facteurs premiers à partir du nombre original, et donc le nombre réduit n'aura pas de facteurs premiers communs avec lui, c'est-à-dire que d ne divisera pas le nombre réduit même s'il divise l'original.

Answer 2

Deux choses :

1) Vous commencez count à 1 au lieu de 2. Tous les nombres entiers sont divisibles par 1.

2) Vous exécutez un algorithme O(n^2) contre un N plutôt grand (ou du moins vous le serez une fois que vous aurez résolu le point #1). Le temps d'exécution sera assez long.

Answer 3

Le but du projet Euler est que les approches les plus évidentes pour trouver la réponse prennent tellement de temps à calculer qu'elles ne valent pas la peine d'être exécutées. De cette façon, vous apprenez à rechercher les approches moins évidentes et plus efficaces.

Votre approche est techniquement correcte pour ce qui est de savoir si elle est capable ou non de calculer le plus grand nombre premier d'un certain nombre. La raison pour laquelle vous ne voyez rien s'imprimer est que votre algorithme n'est pas capable de résoudre le problème rapidement.

De la façon dont vous l'avez conçu, il faudra environ 4 millions d'années pour le terminer.

Si vous remplaciez le nombre 600851475143 par disons 20, il serait capable de terminer assez rapidement. Mais vous avez le nombre 600 milliards, donc ce n'est pas si simple.