Factorisation Programme en Java

Je suis en train de travailler sur une factorisation programme mis en œuvre en Java.
L'objectif est de trouver le plus grand facteur premier de 600851475143 (Projet Euler problème 3).
Je pense que j'ai le plus de faire, mais je suis de faire un peu d'erreurs.
Aussi ma logique semble être hors, en particulier la méthode que j'ai mis en place pour vérifier si un nombre est premier.

public class PrimeFactor {

    public static void main(String[] args) {
        int count = 0;
        for (int i = 0; i < Math.sqrt(600851475143L); i++) {
            if (Prime(i) && i % Math.sqrt(600851475143L) == 0) {
                count = i;
                System.out.println(count);
            }
        }
    }

    public static boolean Prime(int n) {
        boolean isPrime = false;
        //A number is prime iff it is divisible by 1 and itself only
        if (n % n == 0 && n % 1 == 0) {
            isPrime = true;
        }
        return isPrime;
    }
}

Modifier

public class PrimeFactor {

    public static void main(String[] args) {
        for (int i = 2; i <= 600851475143L; i++) {
            if (isPrime(i) == true) {
                System.out.println(i);
            }
        }
    }

    public static boolean isPrime(int number) {
        if (number == 1) return false;
        if (number == 2) return true;
        if (number % 2 == 0) return false;
        for (int i = 3; i <= number; i++) {
            if (number % i == 0) return false;
        }
        return true;
    }
}

Quelles erreurs avez-vous l'obtenir? et dans lequel les lignes ne vous obtenez des erreurs?
Votre Premier méthode renvoie toujours vrai, car n%n == 0 && n%1 == 0 pour tous n. C'est, tous les nombres sont divisibles que par eux-mêmes et 1. Vous êtes absent le "seulement" une partie de la définition.
Malheureusement, vous n'êtes même pas proche. Votre primalité algorithme ne fonctionne pas, parce que tous les nombres sont divisibles que par eux-mêmes et zéro - c'est juste que les nombres premiers ne sont pas divisibles par quoi que ce soit d'autre, et que vous avez à mettre en œuvre une case pour cela. Le Tamis de Erasthones besoins 600 GO de mémoire RAM pour fonctionner jusqu'à une valeur dans la 600B gamme, de manière récursive la factorisation en nombres premiers est la seule pratique de la stratégie, et avec un grand espace de problème, il va prendre des heures ou des jours. C'est la base de tous de cryptage modernes: la factorisation en nombres premiers au-dessus de la taille de la RAM est très lent.
Oui, c'était l'une des erreurs logiques, comment pourrais-je résoudre ce problème?
Je pense que tu veux dire " divisible par eux-mêmes et un ".

OriginalL'auteur kachilous | 2010-11-25

Pourquoi faire si compliqué? Vous n'avez pas besoin faire quelque chose comme isPrime(). Diviser c'est moins diviseur(le premier) et faire la boucle à partir de ce premier. Voici mon code simple :

public class PrimeFactor {

    public static int largestPrimeFactor(long number) {
        int i;

        for (i = 2; i <= number; i++) {
            if (number % i == 0) {
                number /= i;
                i--;
            }
        }

        return i;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        System.out.println(largestPrimeFactor(13195));
        System.out.println(largestPrimeFactor(600851475143L));
    }
}

merci. très simple
Juste un conseil: c'est avec de grands nombres premiers supérieurs à 2147483647 (en Entier.MAX_VALUE) ? Peut-être que vous devez utiliser lors que le type de la variable "i" dans ce cas.
Pourquoi faisons-nous i--?
Êtes-vous tester moi? 😉 Ce cycle prendre des facteurs dans l'ordre, de la plus petite. Un nombre peut être plongé par la même pour plusieurs fois, imaginez 2 * 2 * 2 * 2

OriginalL'auteur

10

edit: j'espère que ce n'est pas un son incroyablement condescendant comme une réponse. Je voulais vraiment l'illustrer à partir de l'ordinateur du point de vue, vous devez vérifier tous les nombres possibles qui pourraient être des facteurs de X pour s'assurer qu'il est premier. Les ordinateurs n'est pas savoir qu'il est composite juste en le regardant, de sorte que vous avez à itérer

Exemple: X Est un nombre premier?

Pour le cas où X = 67:

Comment voulez-vous vérifier?
```
I divide it by 2... it has a remainder of 1 (this also tells us that 67 is an odd number)
I divide it by 3... it has a remainder of 1
I divide it by 4... it has a remainder of 3
I divide it by 5... it has a remainder of 2
I divide it by 6... it has a remainder of 1
```
En fait, vous obtenez seulement un reste de 0 si le nombre n'est pas premier.

Avez-vous de vérifier chaque numéro de moins de X pour s'assurer qu'il est le premier? Nope. Pas plus, grâce aux mathématiques (!)

Regardons un petit nombre, comme 16.

16 n'est pas premier.

pourquoi? parce que
```
2*8 = 16
4*4 = 16
```
Ainsi, le 16 est divisible uniformément plus que 1 et lui-même. (Même si "1" est techniquement pas un nombre premier, mais c'est des détails techniques, et je m'éloigne du sujet)

On divise donc 16 en 1... bien sûr, cela fonctionne, cela fonctionne pour chaque nombre
```
Divide 16 by 2... we get a remainder of 0  (8*2)
Divide 16 by 3... we get a remainder of 1  
Divide 16 by 4... we get a remainder of 0  (4*4)
Divide 16 by 5... we get a remainder of 1
Divide 16 by 6... we get a remainder of 4
Divide 16 by 7... we get a remainder of 2
Divide 16 by 8... we get a remainder of 0  (8*2)
```
Nous avons vraiment seulement besoin d'un reste de 0 pour nous dire qu'il est composite (à l'opposé de "premier" est "composite").

Vérifier si 16 est divisible par 2 est la même chose que de vérifier si il est divisible par 8, parce que le 2 et le 8 se multiplier pour vous donner 16.

Nous avons seulement besoin de vérifier une partie du spectre (à partir de 2 jusqu'à la racine carrée de X) parce que le plus grand nombre que l'on peut multiplier est sqrt(X), sinon, nous sommes en utilisant le plus petit nombre pour obtenir des réponses redondantes.

Est de 17 le premier?
```
17 % 2 = 1
17 % 3 = 2
17 % 4 = 1 <--| approximately the square root of 17 [4.123...]
17 % 5 = 2 <--|
17 % 6 = 5
17 % 7 = 3
```
Les résultats après sqrt(X), comme 17 % 7 et ainsi de suite, sont redondants parce qu'ils doivent nécessairement se multiplient avec quelque chose de plus petit que la sqrt(X) pour un rendement de X.

Qui est,

A * B = X

si A et B sont à la fois plus grande que sqrt(X), alors

A*B produira un nombre qui est plus grand que X.

Ainsi, l'un des deux A ou B doit être plus petite que sqrt(X), et il est superflu de vérifier à la fois de ces valeurs, car vous avez seulement besoin de savoir si l'un d'eux se divise X uniformément (la même division vous donne l'autre valeur comme réponse)

J'espère que ça aide.

edit: Il y a des méthodes plus sophistiquées de la vérification de primalité et Java intégré dans "ce nombre est sans doute le premier" ou "ce nombre est certainement composite" de la méthode dans le La classe BigInteger que j'ai appris récemment par un autre DONC réponse :]

OriginalL'auteur sova
4

Vous avez besoin de faire quelques recherches sur les algorithmes pour factoriser grand nombres; cette page de wikipedia ressemble à un bon endroit pour commencer. Dans le premier paragraphe, il est dit:

Lorsque le nombre est très grand, pas efficace, factorisation d'entiers algorithme est connu ...

mais il ne la liste un certain nombre de spécial et à usage général des algorithmes. Vous devez en choisir un qui fonctionne bien assez à faire avec 12 chiffres décimaux des nombres. Ces nombres sont trop grands pour les plus naïfs d'une approche pour travailler, mais assez petit pour que (par exemple) une approche basée sur l'énumération des nombres premiers à partir de 2 serait de travailler. (Astuce: commencez par le Tamis de Erasthones)

En fait, pour les numéros de cette taille, le plus naïf de la méthode doit toujours être bon. J'ai fait un changement rapide à l'aide de 600852871609, qui est 775147^2, et un naïf test (quoique, en C++ au lieu de Java) donne encore ce qui semble être des résultats immédiats (et le calendrier dit moins de 0,1 seconde).
il dépend de la façon dont naïvement vous tester si chaque nombre est premier. Je vais essayer d'être un peu vague là pour encourager les OP à s'en sortir par lui-même.

OriginalL'auteur Stephen C
4

Ici est très élégant réponse - qui utilise la force brute (pas une fantaisie de l'algorithme), mais de manière intelligente par l'abaissement de la limite que nous trouvons sur les nombres premiers et divisez composite par ces nombres premiers...

Il permet également d'imprimer uniquement les nombres premiers - et les nombres premiers, et si une prime est plus d'une fois dans le produit - elle de l'imprimer autant de fois que le premier est dans le produit.
```
    public class Factorization {
    public static void main(String[] args) {
    long composite = 600851475143L;
    int limit = (int)Math.sqrt(composite)+1;
    for (int i=3; i<limit; i+=2)
    {
        if (composite%i==0)
        {
            System.out.println(i);
            composite = composite/i;
            limit = (int)Math.sqrt(composite)+1;
            i-=2;   //this is so it could check same prime again
        }
    }
    System.out.println(composite);
    }
}
```
Je viens de remarquer qu'il sera totalement manquer facteurs de deux (bien qu'il est facile de voir si le nombre est de même lors de la saisie d'un numéro) - il pourrait y avoir un autre while(composite%2==0) avant de cette boucle pour vérifier combien de fois il a facteur de deux à lui-même...

OriginalL'auteur Stijak
2

Vous souhaitez effectuer une itération à partir de la 2 -> n-1 et assurez-vous que n % i != 0. C'est le plus naïf moyen de vérifier la primalité. Comme expliqué ci-dessus, c'est très très lent si le nombre est grand.

OriginalL'auteur shoebox639
2

De trouver des facteurs, vous voulez quelque chose comme:
```
long limit = sqrt(number);
for (long i=3; i<limit; i+=2)
    if (number % i == 0)
        print "factor = " , i;
```
Dans ce cas, les facteurs sont tous assez petit (<7000) que les trouver devrait prendre moins d'une seconde, même avec naïfs code comme celui-ci. Notez également que ce nombre a d'autres, plus petites, les facteurs premiers. Pour une attaque par force brute comme cela, vous pouvez enregistrer un peu de travail en divisant le plus petit des facteurs que vous les trouvez, et puis faire une factorisation du petit nombre qui en résulte. Ceci a l'avantage de donner uniquement facteurs premiers. Sinon, vous aurez également le composite de facteurs (par exemple, ce nombre a quatre facteurs premiers, de sorte que la première méthode permet d'imprimer non seulement les facteurs premiers, mais les produits de diverses combinaisons de ces facteurs premiers).

Si vous souhaitez optimiser un peu, vous pouvez utiliser le crible d'Eratosthène pour trouver les nombres premiers jusqu'à la racine carrée, et alors seulement la tentative de division par les nombres premiers. Dans ce cas, la racine carrée est d'environ 775'000, et vous avez seulement besoin d'un bit par numéro pour indiquer si c'est le premier. Vous aussi (normalement) souhaitez stocker des nombres impairs (puisque vous savez tout de suite que tous les nombres pairs, mais les deux sont composites), de sorte que vous besoin d'environ 775'000/2 bits = ~47 kilo-octets.

Dans ce cas, qui a peu de réel gain si -- même complètement naïfs algorithme semblent produire des résultats instantanément.

comment voulez-vous savoir que i est premier si votre juste vérifier pour voir si je divise de manière égale en nombre
vous ne voudriez pas. Comme je l'ai dit, ce trouve facteurs, pas seulement de facteurs premiers. J'ai édité la réponse, cependant, ajouter une méthode qui vous permettra d'afficher uniquement les facteurs premiers.
29 est un nombre premier car il n'y a pas moins de 29 divisent en elle. Pas de nombre de 2 à 28 peut diviser les 29 et ne pas avoir un surplus ou d'une fraction de la composante. Ainsi, vous pouvez diviser un nombre par chaque entier ci-dessous pour déterminer s'il est premier ou non. Vous pouvez également remarquer que vous n'avez qu'à le diviser par tous les nombres jusqu'à la racine carrée du nombre que vous êtes vérification, et c'est parce que...[je reviendrai dans une réponse de plus d'espace de mise en forme]

OriginalL'auteur Jerry Coffin
1

Je pense que vous êtes confus car il n'y a pas de forum [si-et-seulement-si] l'opérateur.

Aller à la racine carré de l'entier en question est un bon raccourci. Tout ce qui reste est de vérifier si le nombre à l'intérieur de cette boucle répartit uniformément. C'est tout simplement [nombre] % i == 0. Il n'y a aucune raison pour que votre fonction première.

Depuis que vous êtes à la recherche pour le plus grand diviseur, une autre astuce serait de partir de la plus haute entier inférieur à la racine carrée et aller i--.

Comme d'autres l'ont dit, en fin de compte, c'est brutalement lent.

Vous pouvez toujours vérifier 2, départ à 3 et incrémentation de i par 2 à chaque étape afin de réduire le temps de moitié. Une manière simple d'améliorer cette méthode de détermination de primalité.

OriginalL'auteur amer

    private static boolean isPrime(int k) throws IllegalArgumentException
     {
        int j;

        if (k < 2) throw new IllegalArgumentException("All prime numbers are greater than 1.");
        else {
            for (j = 2; j < k; j++) {
                if (k % j == 0) return false;
            }
        }

        return true;
    }

    public static void primeFactorsOf(int n) {
        boolean found = false;

        if (isPrime(n) == true) System.out.print(n + " ");
        else {
            int i = 2;
            while (found == false) {
                if ((n % i == 0) && (isPrime(i))) {
                    System.out.print(i + ", ");
                    found = true;
                } else i++;
            }
            primeFactorsOf(n / i);
        }
    }

ne peut pas gérer 600851475149.

OriginalL'auteur user2069283

0

Pour ces réponses qui utilisent une méthode isPrime(int) : boolean, il existe un algorithme plus rapide que celui déjà mis en œuvre (qui est en quelque sorte)
```
private static boolean isPrime(long n) { //when n >= 2
    for (int k = 2; k < n; k++)
        if (n % k == 0) return false;

    return true;
}
```
et c'est ceci:
```
private static boolean isPrime(long n) { //when n >= 2
    if (n == 2 || n == 3) return true;

    if (n % 2  == 0 || n % 3 == 0) return false;

    for (int k = 1; k <= (Math.floor(Math.sqrt(n)) + 1) / 6; k++)
        if (n % (6 * k + 1) == 0 || n % (6 * k - 1) == 0) return false;

    return true;
}
```
J'ai fait cet algorithme à l'aide de deux faits:
1. Nous avons seulement besoin de vérifier pour n % k == 0 jusqu'à k <= Math.sqrt(n). Cela est vrai parce que, pour quelque chose de plus élevé, les facteurs simplement "flip" ex. prenons le cas n = 15, où 3 * 5 = 5 * 3, et 5 > Math.sqrt(15). Il n'est pas nécessaire pour ce chevauchement de vérifier à la fois 15 % 3 == 0 et 15 % 5 == 0, quand nous pourrions simplement cocher l'une de ces expressions.
2. Tous les nombres premiers (à l'exclusion des 2 et 3) peut être exprimée sous la forme (6 * k) + 1 ou (6 * k) - 1, parce que tout entier positif peut être exprimé sous la forme (6 * k) + n, où n = -1, 0, 1, 2, 3, or 4 et k est un entier <= 0, et le cas où n = 0, 2, 3, and 4 sont tous réductible.
Par conséquent, n est premier s'il n'est pas divisible par 2, 3, ou certains d'entiers de la forme 6k ± 1 <= Math.sqrt(n). D'où l'algorithme ci-dessus.

--

Article de wikipédia sur les tests de primalité

--

Edit: Pensé que je pourrais aussi bien mettre ma solution complète (*je n'ai pas utilisé isPrime(), et ma solution est presque identique à la réponse sommet, mais j'ai pensé que je dois répondre à la question réelle):
```
public class Euler3 {

    public static void main(String[] args) {
        long[] nums = {13195, 600851475143L};

        for (num : nums)
            System.out.println("Largest prime factor of " + num + ": " + lpf(num));

    }

    private static lpf(long n) {
        long largestPrimeFactor = 1;
        long maxPossibleFactor = n / 2;

        for (long i = 2; i <= maxPossibleFactor; i++)
            if (n % i == 0) {
                n /= i;
                largestPrimeFactor = i;

                i--;
            }

            return largestPrimeFactor;

    }

}
```
BONJOUR, et bienvenue à Débordement de Pile. 🙂 comment sur 600851475149, pouvez-vous trouver deux principales améliorations apportées à votre code afin qu'il puisse factoriser ce nombre, dans un esprit sain laps de temps? (et le haut-voté réponse ici n'est pas bon, comme la plupart du reste d'entre eux, malheureusement).
Salut! Désolé, je n'ai jamais vu de votre commentaire, mais j'ai pensé que mieux vaut tard que jamais. Une chose que j'ai bien serait de créer un début de liste de 0,0,2,3,0,5,0,7,0... et contenant des zéros en place pour tous les éléments à l'exception de ceux de la forme 6k-1 et 6k+1, où le nombre lui-même est assis là, et monter à l'étage(sqrt(n)). Puis, sautant les zéros, en divisant toutes les instances d'un nombre donné, le stockage de ce nombre, puis de le remplacer et tous ses multiples avec des 0. Il combine les 6k-1 et 6k+1 tour, le Crible d'Eratosthène, ainsi que de réduire le nombre maximal de test. Quelles sont les autres trucs qui me manque?
Salut. Vous décrivez une réécriture complète. Je voulais dire, faire deux changements dans long maxPossibleFactor = n / 2; for (long i = 2; i <= maxPossibleFactor; i++){ ... }.
Hmm, peut-être définir maxPossibleFactor = floor(sqrt(n)) et au lieu de i++, diviser les facteurs 2 et 3 d'abord, puis de l'augmenter, j'ai par deux à chaque fois c'est à dire i+=2 (et puis remplacez le i-- à l'intérieur de la boucle avec i=2). En aparté, comment voulez-vous insérer dans les commentaires de texte qui a le code comme format?
augmenter de 2 jusqu'à quand? est la question. pour la mise en forme du code, placez le code dans backticks (`...`). Si le code contient des backticks, mettez en double-backticks.

OriginalL'auteur Ben Colson

Pour trouver toutes factorisation

import java.math.BigInteger;
import java.util.Scanner;


public class BigIntegerTest {


     public static void main(String[] args) {


            BigInteger myBigInteger = new BigInteger("65328734260653234260");//653234254
            BigInteger originalBigInteger;
            BigInteger oneAddedOriginalBigInteger;
            originalBigInteger=myBigInteger;
            oneAddedOriginalBigInteger=originalBigInteger.add(BigInteger.ONE);
            BigInteger index;
            BigInteger countBig;


            for (index=new BigInteger("2");  index.compareTo(myBigInteger.add(BigInteger.ONE)) <0; index = index.add(BigInteger.ONE)){

                countBig=BigInteger.ZERO;
                while(myBigInteger.remainder(index) == BigInteger.ZERO ){
                    myBigInteger=myBigInteger.divide(index);
                    countBig=countBig.add(BigInteger.ONE);
                }

                if(countBig.equals(BigInteger.ZERO)) continue;
                System.out.println(index+ "**" + countBig);

            }
            System.out.println("Program is ended!");
     }
}

OriginalL'auteur OSezer

J'ai eu un problème similaire avec ma programmation de classe. Dans ma classe il a dû calculer pour un nombre saisi. J'ai utilisé une solution très similaire à Stijak. J'ai édité mon code pour faire le nombre à partir de ce problème au lieu de l'aide d'une entrée.

Quelques différences de Stijak du code sont les suivants:

J'ai considéré le même nombre dans mon code.

Mon code affiche seulement le plus grand facteur premier, pas tous les facteurs.

Je n'ai pas recalculer la factorLimit jusqu'à ce que j'ai divisé toutes les instances de l'actuel facteur off.

J'ai eu toutes les variables déclarées comme longtemps parce que je voulais la flexibilité de l'utiliser pour de grandes valeurs de nombre. J'ai trouvé le scénario du pire a été d'un très grand nombre premier comme 9223372036854775783, ou un très grand nombre avec un nombre premier de la racine carrée comme 9223371994482243049. Plus nombreux sont les facteurs d'un nombre est le plus rapide de l'algorithme s'exécute. Par conséquent, le meilleur scénario serait de tels chiffres 4611686018427387904 (2^62) ou 6917529027641081856 (3*2^61) parce que les deux ont 62 facteurs.

public class LargestPrimeFactor
{
    public static void main (String[] args){
        long number=600851475143L, factoredNumber=number, factor, factorLimit, maxPrimeFactor;
        while(factoredNumber%2==0)
            factoredNumber/=2;
        factorLimit=(long)Math.sqrt(factoredNumber);
        for(factor=3;factor<=factorLimit;factor+=2){
            if(factoredNumber%factor==0){
                do  factoredNumber/=factor;
                while(factoredNumber%factor==0);
                factorLimit=(long)Math.sqrt(factoredNumber);
            }
        }
        if(factoredNumber==1)
            if(factor==3)
                maxPrimeFactor=2;
            else
                maxPrimeFactor=factor-2;
        else
            maxPrimeFactor=factoredNumber;
        if(maxPrimeFactor==number)
            System.out.println("Number is prime.");
        else
            System.out.println("The largest prime factor is "+maxPrimeFactor);
    }
}

OriginalL'auteur Steven Smith

public class Prime
{
int i;   
public Prime( )
{
i = 2;
}
public boolean isPrime( int test ) 
{
int k;
if( test < 2 )
return false;
else if( test == 2 )  
return true;
else if( ( test > 2 ) && ( test % 2 == 0 ) )
return false;
else
{
for( k = 3; k < ( test/2 ); k += 2 )
{
if( test % k == 0 ) 
return false;
}
}
return true;
}
public void primeFactors( int factorize )
{
if( isPrime( factorize ) )
{
System.out.println( factorize );
i = 2;
}
else
{
if( isPrime( i ) && ( factorize % i == 0 ) )
{
System.out.print( i+", " );
primeFactors( factorize / i );
}
else
{
i++;
primeFactors( factorize );
}
}
public static void main( String[ ] args )
{
Prime p = new Prime( );
p.primeFactors( 649 );
p.primeFactors( 144 );
p.primeFactors( 1001 );
}
}

OriginalL'auteur user2710322

Vous devez vous connecter pour publier un commentaire.