Aide de Project Euler Question 3

Question

J'essaie de travailler avec Project Euler et je rencontre une barrière pour le problème 03. J'ai un algorithme qui fonctionne pour les petits nombres, mais le problème 3 utilise un très très grand nombre.

Problème 03: Les facteurs premiers de 13195 sont 5, 7, 13 et 29. Quel est le plus grand facteur premier du nombre 600851475143?

Voici ma solution en C # qui fonctionne depuis près d’une heure, je pense. Je ne cherche pas de réponse car je souhaite résoudre ce problème moi-même. Je cherche principalement de l’aide.

    static void Main(string[] args) {
        const long n = 600851475143;
        //const long n = 13195;
        long count, half, largestPrime = 0;
        bool IsAPrime;

        half = n / 2;

        for (long i = half; i > 1 && largestPrime == 0; i--) {
             if (n % i == 0) { // these are factors of n
                count = 1;
                IsAPrime = true;
                while (++count < i && IsAPrime) {
                    if (i % count == 0) { // does a factor of n have a factor? (not prime)
                        IsAPrime = false;
                    }
                }
                if (IsAPrime) {
                    largestPrime = i;
                }
            }
        }

        Console.WriteLine("The largest prime factor is " + largestPrime.ToString() + ".");
        Console.ReadLine();
    }

Answer 1

Pour commencer, au lieu de commencer votre recherche à n / 2, démarrez-la à la racine carrée de n. Vous obtiendrez la moitié des facteurs, l'autre moitié leur complément.

par exemple:

n = 27
start at floor(sqrt(27)) = 5
is 5 a factor? no
is 4 a factor? no
is 3 a factor? yes. 27 / 3 = 9. 9 is also a factor.
is 2 a factor? no.
factors are 3 and 9.

Answer 2

long n = 600851475143L; //not even, so 2 wont be a factor
int factor = 3; 
while( n > 1)
{
    if(n % factor == 0)
    {
        n/=factor;
    }else
        factor += 2; //skip even numbrs
}
        print factor;

Cela devrait être assez rapide ... Remarquez, il n'est pas nécessaire de vérifier le nombre de premiers ...

Answer 3

En fait, dans ce cas, vous n'avez pas besoin de vérifier la primalité, supprimez simplement les facteurs que vous avez trouvés. Commencez avec n == 2 et balayez vers le haut. Lorsque mal-grand-nombre% n == 0, divisez mal-grand-nombre par n et continuez avec un nombre plus petit. Arrêtez-vous lorsque n > = sqrt (big-evil-number).

Ne devrait pas prendre plus de quelques secondes sur n’importe quelle machine moderne.

Answer 4

Bien que la question demande le plus grand facteur premier, cela ne signifie pas nécessairement que vous devez trouver celui-là en premier ...

Answer 5

Vous devez réduire le nombre de vérifications que vous effectuez ... réfléchissez aux nombres que vous devez tester.

Pour une meilleure approche, consultez le Sieve of Erathosthenes ... vous avez indiqué la bonne direction.

Answer 6

En ce qui concerne la raison de la réponse de nicf acceptée:

Le problème chez Euler est acceptable, mais ne constitue pas une solution efficace dans le cas général. Pourquoi voudriez-vous essayer même des nombres pour les facteurs?

• Si n est pair, décaler à gauche (diviser par 2) jusqu'à ce que ce ne soit plus. Si c'est on alors, 2 est le plus grand nombre premier facteur.
• Si n n'est pas pair, vous n'avez pas à tester les nombres pairs.
• Il est vrai que vous pouvez vous arrêter à sqrt (n).
• Il suffit de tester les nombres premiers pour les facteurs. Il pourrait être plus rapide de tester si k divise n et ensuite le tester pour la primalité si.
• Vous pouvez optimiser la limite supérieure de la mouche quand vous trouvez un facteur.

Cela conduirait à un code comme celui-ci:

n = abs(number);
result = 1;
if (n mod 2 = 0) {
  result = 2;
  while (n mod 2 = 0) n /= 2;
}
for(i=3; i<sqrt(n); i+=2) {
  if (n mod i = 0) {
    result = i;
    while (n mod i = 0)  n /= i;
  }
}
return max(n,result)

Certains tests modulo sont superflous, car n ne peut jamais être divisé par 6 si tous les facteurs 2 et 3 ont été supprimés. Vous ne pouvez autoriser que les nombres premiers pour i.

À titre d'exemple, regardons le résultat pour 21:

21 n’est pas pair, nous allons donc dans la boucle for avec une limite supérieure sqrt (21) (~ 4.6). On peut alors diviser 21 par 3, donc result = 3 et n = 21/3 = 7. Il ne reste plus qu’à tester jusqu’à sqrt (7). qui est plus petit que 3, nous en avons donc terminé avec la boucle for. Nous renvoyons le maximum de n et le résultat, qui est n = 7.

Answer 7

Pour y arriver, j'ai recherché des nombres premiers ( p ), en commençant à 2 à l'aide du tamis d'Eratosthène. Cet algorithme peut trouver tous les nombres premiers inférieurs à 10 millions en <2 sur une machine assez rapide.

Pour chaque nombre premier que vous trouvez, testez-le en le divisant par le nombre que vous testez jusqu'à ce que vous ne puissiez plus diviser en nombres entiers. (c.-à-d. vérifiez n% p == 0 et si vrai, divisez.)

Une fois que n = 1 , vous avez terminé. La dernière valeur de n ayant été divisée avec succès est votre réponse. Dans un résumé, vous avez également trouvé tous les facteurs premiers de n en cours de route.

PS: comme indiqué précédemment, il vous suffit de rechercher des nombres premiers entre 2 < = n < = sqrt (p) . Cela fait du Sieve of Eratosthenes un algorithme très rapide et facile à mettre en œuvre pour nos besoins.

Answer 8

Une fois que vous avez trouvé la réponse, entrez les informations suivantes dans votre navigateur;)

http://www.wolframalpha.com/input/?i= FactorInteger (600851475143)

Wofram Alpha est votre ami

Answer 9

L'utilisation d'un algorithme récursif en Java prend moins d'une seconde ... réfléchissez un peu à votre algorithme, car il inclut des "forçage brutal". cela peut être éliminé. Regardez également comment votre espace de solution peut être réduit par des calculs intermédiaires.

Answer 10

Peasy facile en C ++:

#include <iostream>

using namespace std;


int main()
{
    unsigned long long int largefactor = 600851475143;
    for(int i = 2;;)
    {
        if (largefactor <= i)
            break;
        if (largefactor % i == 0)
        {
            largefactor = largefactor / i;
        }
        else
            i++;
    }

    cout << largefactor << endl;

    cin.get();
    return 0;
}

Answer 11

Cette solution en C ++ a pris 3,7 ms sur mon iMac Intel Quad Core i5 (3,1 GHz)

#include <iostream>
#include <cmath>
#include <ctime>

using std::sqrt; using std::cin;
using std::cout; using std::endl;

long lpf(long n)
{
  long start = (sqrt(n) + 2 % 2);
  if(start % 2 == 0) start++;

  for(long i = start; i != 2; i -= 2)
    {
      if(n % i == 0) //then i is a factor of n                                                
        {
          long j = 2L;
          do {
              ++j;
             }
          while(i % j != 0 && j <= i);

          if(j == i) //then i is a prime number                                           
            return i;
        }
    }
}

int main()
{
  long n, ans;
  cout << "Please enter your number: ";
  cin >> n; //600851475143L                                                               

  time_t start, end;
  time(&start);
  int i;
  for(i = 0; i != 3000; ++i)
      ans = lpf(n);
  time(&end);

  cout << "The largest prime factor of your number is: " << ans << endl;
  cout << "Running time: " << 1000*difftime(end, start)/i << " ms." << endl;

  return 0;
}

Answer 12

Tous les problèmes du projet Euler devraient prendre moins d'une minute; même une implémentation récursive non optimisée en Python prend moins d’une seconde [0,09 s (CPU 4,3 GHz)].

from math import sqrt

def largest_primefactor(number):
    for divisor in range(2, int(sqrt(number) + 1.5)): # divisor <= sqrt(n)
        q, r = divmod(number, divisor)
        if r == 0:
            #assert(isprime(divisor))
            # recursion depth == number of prime factors,
            # e.g. 4 has two prime factors: {2,2}
            return largest_primefactor(q) 

    return number # number is a prime itself

Answer 13

vous voudrez peut-être voir ceci: Existe-t-il un algorithme simple permettant de déterminer si X est primordial et de ne pas confondre un simple programmeur mortel?

et j'aime bien la solution de lill mud:

  

require "mathn.rb"
  met 600851475143.prime_division.last.first

Je l'ai vérifié ici

Answer 14

C’est peut-être considéré comme de la triche, mais une des possibilités de haskell est d’écrire (pour mémoire, j’ai écrit les lignes moi-même et je n’ai pas vérifié les threads eulerproject);

import Data.Numbers.Primes
last (primeFactors 600851475143)

Answer 15

Essayez d'utiliser le test de primalité Miller-Rabin pour tester le nombre premier. . Cela devrait considérablement accélérer les choses.

Answer 16

Une autre approche consiste à obtenir tous les nombres premiers jusqu’à n / 2 d’abord, puis à vérifier si le module est égal à 0. Un algorithme que j'utilise pour obtenir tous les nombres premiers jusqu'à n est disponible ici .