Projet Euler Question 3 Aide

Je suis en train de travailler à travers le Projet Euler et je suis de heurter un obstacle sur le problème de 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:
Le premier des facteurs de 13195 sont 5, 7, 13 et 29.
Quel est le plus grand facteur premier de le nombre 600851475143?

Voici ma solution en C# et ça fonctionne car je pense que près d'une heure. Je ne suis pas à la recherche d'une réponse, parce que je ne veux réellement à résoudre moi-même. Principalement à la recherche 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();
    }

source d'informationauteur Ryan Rodemoyer

algorithm c#language-agnostic primes

Pour commencer, au lieu de commencer votre recherche à n /2, départ à la racine carrée de n. Vous aurez la moitié des facteurs, l'autre moitié étant son 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.

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...Avis, il n'y a pas besoin de vérifier, pour le premier...

10

En fait, dans ce cas, vous n'avez pas besoin de vérifier la primalité, il suffit de retirer les facteurs que vous trouvez. Commencer avec n == 2 et balayez vers le haut. Lorsque le mal-grand-nombre % n == 0, diviser le mal-grand-nombre par n et continuer avec les petits-mal-nombre. Arrêter quand n >= sqrt(grand-mal-nombre).

Ne devrait pas prendre plus de quelques secondes sur n'importe quel machine moderne.
10

Bien que la question demande la plus grand premier facteur, il ne signifie pas nécessairement que vous avez à trouver que la première...
6

Vous besoin de réduire la quantité de vérification que vous êtes en train de faire ... pensez à ce que les numéros que vous devez tester.

Pour une meilleure approche de lire sur le Tamis de Erathosthenes ... il devrait vous obtenir pointé dans la bonne direction.
3

Que pour la raison acceptées nicf réponse:

C'est OK pour le problème d'Euler, mais n'en fait pas une solution efficace dans le cas général. Pourquoi voulez-vous essayer le même nombre de facteurs?
- Si n est pair, la touche maj de gauche (diviser par
  2) jusqu'à ce qu'il n'est pas plus. Si c'est
  alors, de 2 est le plus grand nombre premier
  facteur.
- Si n n'est pas le même, vous n'avez pas à
  l'épreuve des chiffres.
- Il est vrai que vous pouvez vous arrêter à
  sqrt(n).
- Vous n'avez qu'à tester les nombres premiers pour
  facteurs. Il pourrait être plus rapide pour tester
  si k divise n et puis le tester
  pour de primalité.
- Vous pouvez optimiser la limite supérieure de la
  la volée lorsque vous trouvez un facteur.
Cela conduirait à un code comme ceci:
```
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)
```
Il y a quelques modulo tests de superflu, que n ne peut jamais être divisé par 6 si tous les facteurs 2 et 3 ont été supprimés. Vous ne pouviez vous permettre de nombres premiers pour je.

Comme un exemple permet de regarder la suite pour 21:

21 n'est pas la même, de sorte que nous allons dans la boucle avec la limite supérieure sqrt(21) (~4.6).
On peut alors diviser 21 par 3, donc résultat = 3 et n = 21/3 = 7. Aujourd'hui, nous n'avons pour tester jusqu'à sqrt(7). ce qui est plus petit que 3, donc nous avons fait avec la boucle for. Nous retourner le max de n et de résultat, qui est n = 7.
2

La façon dont je l'ai fait il était à la recherche de nombres premiers (p), en commençant à 2 à l'aide du Crible d'Eratosthène. Cet algorithme permet de trouver tous les nombres premiers inférieurs à 10 millions en <2s sur un décemment rapide de la machine.

Pour chaque prime, vous trouver, tester la diviser en fonction du nombre que vous testez jusqu'à ce que vous ne pouvez pas faire de division entière plus. (ie. vérifier n % p == 0 et si la valeur est true, puis de diviser.)

Une fois n = 1vous avez terminé. La dernière valeur de n qui ont réussi à diviser est votre réponse. Sur une note, vous avez aussi trouvé tous les facteurs premiers de n sur le chemin.

PS: Comme cela a été indiqué précédemment, vous avez seulement besoin de recherche de nombres premiers entre 2 <= n <= sqrt(p). Cela rend le Crible d'Eratosthène est très rapide et facile à mettre en œuvre l'algorithme pour nos fins.
2

Une fois que vous trouvez la réponse, saisissez le texte suivant dans votre navigateur 😉

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

Wofram Alpha est votre ami
1

À l'aide d'un algorithme récursif en Java s'exécute en moins d'une seconde ... pensez que votre algorithme à travers un peu, car il comprend quelques "brute-force" qui peut être éliminé. Aussi regarder comment votre espace de solution peut être réduit par l'intermédiaire de calculs.

Easy peasy 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;
}

Cette solution sur le C++ a pris 3.7 ms sur mon Intel Quad Core i5 iMac (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;
}

Tout Projet Euler problèmes devrait prendre moins d'une minute; même un unoptimized récursive de la mise en œuvre en Python prend moins d'une seconde [0.09 secondes (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

0

vous pourriez voir ceci:
Est-il un algorithme simple qui permet de déterminer si X est premier, et ne pas confondre un simple mortel programmeur?

et j'aime lill de la boue de la solution:

besoin "mathn.rb"

met 600851475143.prime_division.dernier.première

Je l'ai vérifié ici
0

Peut-être que c'est considéré comme de la triche, mais une possibilité en haskell est d'écrire (pour l'enregistrement, j'ai écrit les lignes de moi-même et n'ai pas vérifié eulerproject threads);
```
import Data.Numbers.Primes
last (primeFactors 600851475143)
```
-1

Essayez d'utiliser le De Miller-Rabin Test De Primalité pour tester un nombre premier. Qui devrait réduire considérablement les choses.
-1

Une autre approche est d'obtenir tous les nombres premiers jusqu'à n/2 en premier, puis de vérifier si le module est de 0.
Un algorithme pour obtenir tous les nombres premiers jusqu'à n peut être trouvé ici.

Vous devez vous connecter pour publier un commentaire.