Projekt Euler Frage 3 Hilfe

Question

Ich versuche, durch Projekt Euler zu arbeiten, und ich bin eine Barriere auf Problem 03. Schlage Ich habe einen Algorithmus, der für kleinere Zahlen funktioniert, aber Problem 3 verwendet eine sehr, sehr große Zahl.

Problem 03: Die Primfaktoren von 13195 sind 5, 7, 13 und 29. Was ist der größte Primfaktor der Nummer 600851475143?

Hier ist meine Lösung in C # und es läuft seit ich zu einer Stunde schließen denken. Ich bin nicht auf der Suche nach einer Antwort, weil ich wirklich will dies selbst zu lösen. In erster Linie nur für einige Hilfe suchen.

    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

Für den Anfang, statt der Suche beginnen bei n / 2, es an der Quadratwurzel von n starten. Sie werden die Hälfte der Faktoren bekommen, die andere Hälfte ihrer Ergänzung.

Beispiel:

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;

Dies sollte schnell genug sein ... Hinweis, es gibt keine Notwendigkeit für prim zu überprüfen ...

Answer 3

Eigentlich für diesen Fall brauchen Sie nicht für primality zu überprüfen, entfernen Sie einfach die Faktoren, die Sie finden. Beginnen Sie mit n == 2 und Scan nach oben. Wenn die Böse-big-Zahl% n == 0, teilen böse-big-Zahl von n und weiterhin mit kleineren Übel-Nummer. Stoppen Sie, wenn n> = sqrt (big-Übel-Nummer).

sollte nicht länger als ein paar Sekunden auf jeder modernen Maschine.

Answer 4

Auch wenn die Frage geht dahin, für die größte Primfaktor, ist es nicht unbedingt, dass Sie, dass man finden muss zuerst ein ...

Answer 5

Sie müssen die Menge des Prüfens Sie tun ... darüber nachdenken, zu reduzieren, welche Zahlen Sie brauchen, um zu testen.

Für einen besseren Ansatz lesen Sie auf der Seite Sieve von Erathosthenes ... sollte es bekommen Sie wies in die richtige Richtung.

Answer 6

Wie aus dem Grund, akzeptiert NICF Antwort:

Es ist für das Problem bei Euler OK, aber nicht diese eine effiziente Lösung im allgemeinen Fall machen. Warum würden Sie gerade Zahlen für Faktoren versuchen?

• Wenn n gerade ist, verschieben sich nach links (Division durch 2), bis es nicht mehr. Wenn es man dann, 2 ist die größte Primzahl Faktor.
• Wenn n nicht gerade ist, müssen Sie nicht auf Test gerade Zahlen.
• Es ist wahr, dass Sie aufhören können sqrt (n).
• Sie haben nur Primzahlen zu testen Faktoren. Es könnte schneller sein zu testen ob k n teilt und dann testen, für primality though.
• Sie können die obere Grenze optimieren auf die Fliege, wenn Sie einen Faktor finden.

Dies zu einem gewissen Code wie folgt führen:

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)

Es gibt einige Modulo-Tests, die superflous sind, wie n niemals durch 6 geteilt werden, wenn alle Faktoren 2 und 3 wurden entfernt. Sie könnten nur erlauben Primzahlen für i.

Wie ein Beispiel zu dem Ergebnis aussehen läßt für 21:

21 ist nicht einmal, also gehen wir in die for-Schleife mit Obergrenze sqrt (21) (~ 4.6). Wir können dann 21 durch 3 teilen daher führen = 3 und n = 21/3 = 7. Wir haben jetzt nur sqrt zu testen, müssen (7). die kleiner als 3, so dass wir mit der for-Schleife durchgeführt. Wir kehren das Maximum von n und Ergebnis, das n = 7.

Answer 7

So wie ich es tat, war für Primzahlen (p) zu suchen, bei 2 Starten des Sieb des Eratosthenes verwenden. Dieser Algorithmus kann alle Primzahlen unter 10 Millionen in <2s auf einer anständig schnelle Maschine finden.

Für jede Primzahl finden, Test teilt sie in die Nummer, die Sie gegen testen sind, bis Sie Integer-Division nicht mehr tun können. (Dh. Überprüfen n % p == 0 und wahr, wenn, dann teilen.)

Sobald n = 1, sind Sie fertig. Der letzte Wert von n, die erfolgreich geteilt ist Ihre Antwort. Auf Nebenbei bemerkt haben, Sie finden auch alle Primfaktoren von n auf dem Weg.

PS: Wie bereits erwähnt, müssen Sie nur für Primzahlen zwischen 2 <= n <= sqrt(p) suchen. Dies macht das Sieb des Eratosthenes eine sehr schnelle und einfache Algorithmus für unsere Zwecke zu implementieren.

Answer 8

Wenn Sie die Antwort zu finden, geben Sie in Ihrem Browser;)

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

Wofram Alpha ist dein Freund

Answer 9

einen rekursiven Algorithmus in Java verwenden läuft weniger als eine Sekunde ... denken, dass Ihr Algorithmus durch ein wenig, wie es einige „Brute-Forcing“ enthält, die beseitigt werden können. Betrachten Sie auch, wie Sie Ihren Lösungsraum kann durch Zwischenberechnungen reduziert werden.

Answer 10

Kinderleicht in 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

Diese Lösung auf C ++ nahm 3,7 ms auf meinem 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;
}

Answer 12

Alle Probleme Project Euler sollte weniger als einer Minute; auch eine nicht optimierte rekursive Implementierung in Python dauert weniger als eine Sekunde [0,09 Sekunden (CPU 4.3GHz)].

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

Sie können diese sehen: Gibt es einen einfachen Algorithmus, der bestimmen kann, wenn X eine Primzahl ist, und kein Sterblicher Programmierer verwirren?

und Ich mag Lill Schlamm-Lösung:

  

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

Ich habe es hier

Answer 14

Vielleicht ist es Betrug betrachtet, sondern eine Möglichkeit, in Haskell ist (für die Platte, die ich die Zeilen selbst geschrieben hätte und nicht eulerproject Fäden geprüft) zu schreiben;

import Data.Numbers.Primes
last (primeFactors 600851475143)

Answer 15

Versuchen Sie die Miller-Rabin-Test unter Verwendung von für eine Zahl ist prim zu testen . Das sollte die Dinge erheblich beschleunigen.

Answer 16

Ein weiterer Ansatz ist es, alle Primzahlen erhalten bis zu n / 2 und dann zu prüfen, ob die Modul 0 ist. Ein Algorithmus ich auf alle Primzahlen erhalten verwenden, um n können hier .