Was ist falsch an meinem code?

[Leonidas]

Kennen auch die modernen Pascal Varianten(FreePascal) keine Listen oder dyn. Arrays?

Wer hat denn was von modernen Varianten gesagt? Wenns nicht in Turbo Pascal 7 läuft, dannn ists nicht ernstzunehmen

[BlackJack]

@darktrym: Es gibt dynamische Arrays in FP (und Delphi), aber damit wird es nicht wirklich besser. Jedenfalls nicht wenn man es mit einer Python-Lösung vergleicht:

Code: Alles auswählen

program Factor;

type
  TPrimeGen = record
    primes : array of Longword;
    candidate : Longword;
    first : Boolean;
  end;

var primeGen : TPrimeGen;
    prime : Longword;
    n : QWord;
    code : Integer;

procedure InitPrimeGen(); inline;
begin
  SetLength(primeGen.primes, 1);
  primeGen.primes[0] := 2;
  primeGen.candidate := 3;
  primeGen.first := true;
end;

procedure DestroyPrimeGen();
begin
  SetLength(primeGen.primes, 0);
end;

function NextPrime():Longword;
var isPrime:Boolean;
    i:Integer;
begin
  if primeGen.first then begin
    NextPrime := 2;
    primeGen.first := false;
  end
  else begin
    repeat
      isPrime := true;
      i := Low(primeGen.primes);
      while (i < High(primeGen.primes)) AND isPrime do
      begin
        if (primeGen.candidate MOD primeGen.primes[i]) = 0 then
          isPrime := false;
        Inc(i);
      end;
      if isPrime then begin
        NextPrime := primeGen.candidate;
        SetLength(primeGen.primes, Length(primeGen.primes) + 1);
        primeGen.primes[High(primeGen.primes)] := NextPrime;
      end;
      Inc(primeGen.candidate, 2);
    until isPrime;
  end;
end;
    
begin
  if ParamCount < 1 then WriteLn('usage: factor number')
  else begin
    Val(ParamStr(1), n, code);
    if code <> 0 then WriteLn('Not a valid number: ', ParamStr(1))
    else begin    
      InitPrimeGen;
      while n > 1 do
      begin
        prime := NextPrime;
        if (n MOD prime) = 0 then begin
          WriteLn(prime);
          while (n > 1) AND ((n MOD prime) = 0) do n := n DIV prime;
        end;
      end;
      DestroyPrimeGen;
    end;
  end;
end.

Das dürfte ausserdem ineffizient sein, denn für jetzes ”append” an das Primzahlen-Array muss potentiell der gesamte bisherige Inhalt umkopiert werden.

Wenn man das nicht haben möchte, dann kann man `TList` oder `TObjectList` verwenden. Ersteres verwaltet eine Liste von Zeigern, letzteres eine Liste von Objekten (und damit letztlich auch von Zeigern). Man muss also die Speicherverwaltung für die Zahlen einzeln übernehmen. Zumindest das anfordern von Speicher für jede einzelne Primzahl. Oder man braucht eine Klasse die einzig und alleine eine ganze Zahl kapselt.

[Gwunderi]

Hallo zusammen,

Habe auch ein paar Anmerkungen:
Will man prüfen, OB eine Zahl n eine Primzahl ist, genügt es, bis zur Wurzel von n zu prüfen.
Aber um die grösste Primzahl, die Teiler von n ist herauszufinden genügt es nicht, habe ich eben herausgefunden.
Nehmen wir z.B. 33 - ist 33 eine Primzahl? da genügt es, bis 6 zu prüfen, denn 11 * 3 wurde schon bei der 3 geprüft.
Aber die grösste Primzahl, die Teiler von 33 ist - also 11 - würde man hier glatt "übersehen".

Man muss also doch, wie BlackJack anfangs meinte, bis n/2 prüfen!

@ Eliazz
Vielleicht wäre Dein Programm effizienter, wenn Du in Deiner Liste "prime_proof" die 21 mit der 19 austauschen würdest, oder? (gibt zwar dieselben Lösungen aus, aber nur weil diese zufällig kein Vielfaches von 19 sind).

Habe auch nicht verstanden, warum Du nur bis zur 37 prüfst, und warum von den 7 ausgegebenen Möglichkeiten die 6857 die richtige sein soll. 486847 ist doch auch eine Primzahl und Teiler von 600'851'475'143?

Habe Dein Programm auch etwas abgeändert, so dass es die ganze Zahlenliste auf einmal prüft (anstatt if ... and if ... and if ...). Hat den Vorteil, dass man die Array ändern oder beliebig verlängern kann, ohne in den Bedingungen dieselben Änderungen vornehmen zu müssen. Unten der Code, der die selben Lösungen wie Deine ausgibt (aber eben nicht die grösste Primzahl, die Teiler von n ist):

Code: Alles auswählen

prime_proof = [3,5,7,11,13,17,19,23,29,31,37]
p_solutions = []
a = 3
while a <= 775147: # 775147 ungefähr Wurzel von 600851475143...
    for x in prime_proof:
        if a%x > 0 and 600851475143%a == 0:
            if a not in p_solutions:
                p_solutions.append(a)
    a = a + 2
print(p_solutions)

[Sirius3]

@Gwunderi: 486847 = 71*6857

[Gwunderi]

@Gwunderi: 486847 = 71*6857

Hallo Sirius,

Ja, stimmt. Erst dachte ich, es sei, weil wir nur bis 37 geprüft haben. Also habe ich 71 zur Array hinzugefüht, aber die 486'847 wird trotzdem ausgegeben. Was stimmt da nicht?

In der Schleife wird doch jetzt auch geprüft:
if 486847 % 71 > 0,
d.h. falls 486847 KEIN Vielfaches von 71 ist, dann gib es aus.
Sollte also gar nicht ausgegeben werden?

Wo ist da mein Denkfehler???

[Sirius3]

@Gwunderi: Durch Deine for-Schleife hast Du die »and«-Verknüpfung in eine »or«-Verknüpfung umgewandelt.

[snafu]

Mal (wenig spektakulär) in Java, wobei ich die Optimierung mit der Quadratwurzel rausgelassen habe und stattdessen immer die Primzahlen bis n/2 ermittle:

Code: Alles auswählen

import java.util.*;

public class PrimeCalculator {
    
    public static List<Integer> getPrimes(int limit) {
        List<Integer> primes = new ArrayList<Integer>();
        if (limit < 2) {
            return primes;
        }
        primes.add(2);
        
        for (int i = 3; i <= limit; i += 2) {
            boolean isPrime = true;
            for (int prime : primes) {
                if (i % prime == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                primes.add(i);
            }
        }
        return primes;
    }
    
    public static int getLargestPrimeFactor(int n) {
        if (n < 2) {
            throw new IllegalArgumentException("n must be >= 2");
        }
        List<Integer> candidates = getPrimes(n / 2);
        Collections.reverse(candidates);
        
        int result = -1;
        for (int candidate : candidates) {
            if (n % candidate == 0) {
                result = candidate;
                break;
            }
        }
        return result;
    }
    
    public static void main(String[] args) {
        System.out.println(getLargestPrimeFactor(111));
    }
}

EDIT: Meine Implementierung enthält noch Fehler, merk ich gerade...

[jerch]

@"Optimierung bis Quadratwurzel"
Wenn man direkt über die schon gefundenen Teiler geht, ist ja die Wurzel nur die obere Suchgrenze, welche mit jedem Teiler nach unten wandert, da man mit dem Quotienten weiterrechnen kann. Hier bietet sich auch die nochmalige Prüfung des Teilers an, um den Exponenten gleich mit zu finden.

@snafu:
An dem Sieb lässt sich aber noch einiges optimieren

[snafu]

@jerch: Das mit der oberen Suchgrenze verstehe ich nicht. Es wurde ja schon angesprochen, dass es desöfteren Situationen gibt, wo der größte Primfaktor *größer* als die Quadratwurzel ist (z.B. bei 77). Wie würde man da im Detail vorgehen?

@snafu:
An dem Sieb lässt sich aber noch einiges optimieren

Jepp. Auf meinem Rechner sorgt schon die Ausführung mit größeren 6-stelligen Zahlen eine spürbare Wartezeit.

[Sirius3]

@snafu: die ganze Suche nach Primzahlen ist völlig überflüssig (siehe meinen Beitrag oben).
Hier mal mit einem duzend Assemblerbefehlen zur Demonstration:

Code: Alles auswählen

# input %rax = number to factor
# output %rax = largest prime factor
primfac:
        movq $2, %rcx
        jmp _start
_loop:
        xorq    %rdx, %rdx
        divq    %rcx
        orq     %rdx, %rdx
        jne     _cont
_start:
        cvtsi2sdq       %rax, %xmm0
        sqrtsd  %xmm0, %xmm0
        cvttsd2siq      %xmm0, %rdi
        movq    %rax, %rsi
        jmp     _test
_cont:
        incq    %rcx
        movq    %rsi, %rax
_test:
        cmpq    %rdi, %rcx
        jle     _loop
        ret

[snafu]

Nochmal Java. Diesmal habe ich mich an Fermat orientiert und hoffentlich nichts übersehen.

Code: Alles auswählen

public class PrimeCalculator {
    
    public static int getLargestPrimeFactor(int n) {
        while (n % 2 == 0) {
            n /= 2;
        }
        int result = 2;
        for (int i = (int) Math.sqrt(n); i < n; i++) {
            double j = Math.sqrt(i * i - n);
            if (j == (int) j) {
                // Quadratzahl gefunden
                result = i + (int) j;
                break;
            }
        }
        return result;
    }
    
    public static void main(String[] args) {
        System.out.println(getLargestPrimeFactor(486847));
    }
}

[Sirius3]

@snafu: nicht ganz. Was passiert, wenn der größte Primfaktor nicht größer als die Wurzel von n ist?

[jerch]

@jerch: Das mit der oberen Suchgrenze verstehe ich nicht. Es wurde ja schon angesprochen, dass es desöfteren Situationen gibt, wo der größte Primfaktor *größer* als die Quadratwurzel ist (z.B. bei 77). Wie würde man da im Detail vorgehen?

Da es maximal einen Primfaktor größer sqrt(n) geben kann, kannst Du diesen ganz leicht ausrechnen: p_max = n / (p_1^a * p_2^b ...)
Wenn Du mit dem Quotienten weiterrechnest, erhältst Du ihn quasi automatisch (Quotient wird entweder 1, dh. Du hast alle unterhalb gefunden, oder eben dieser Faktor).

[BlackJack]

Von mir noch mal eine Lösung mit Primzahlen erzeugen in JavaScript, als Kontrast zum Pascal-Programm mit der selben Grundidee:

Code: Alles auswählen

#!/usr/bin/env node
'use strict';
var _ = require('underscore');

var createPrimeGenerator = function () {
    var primes = [2];
    var candidate = 1;
    var testCandidate = function (prime) { return candidate % prime != 0; };
    var next = function () {
        next = function () {
            while (true) {
                candidate += 2;
                if (_(primes).every(testCandidate)) {
                    primes.push(candidate);
                    return candidate;
                }
            }
        };
        return 2;
    };
    return function () { return next(); };
}

var factor = function (n) {
    var result = [];
    var getNextPrime = createPrimeGenerator();
    while (n > 1) {
        var prime = getNextPrime();
        if (n % prime == 0) {
            result.push(prime);
            while (n > 1 && n % prime == 0) n /= prime;
        }
    }
    return result;
}

var main = function () {
    console.log(factor(parseInt(process.argv[2])));
};

main();

@Sirius3: Ich glaube den ersten Befehl nach dem `_loop`-Label kann man weglassen. `%rdx` wird von der Division danach doch sowieso gleich wieder mit einem anderen Wert überschrieben und die Eingaben für ``divq`` müssten in diesem Fall doch nur `%rax` und `%rcx` sein, oder?

[jerch]

Den generativen Ansatz kann man noch in der Laufzeit verbessern, wenn man auf 2*3 oder 2*3*5 aligned Pattern geht. Quasi Atkin-light

[Gwunderi]

Durch Deine for-Schleife hast Du die »and«-Verknüpfung in eine »or«-Verknüpfung umgewandelt.

Ach so, und da alle anderen geprüften Zahlen keine Teiler von 486'847 sind, wird sie ausgegeben. Hatte ja schon gesehen, dass die Lösungen gleich mehrfach ausgegeben werden, dachte mir aber, es sei weil jetzt jede Zahl einzeln geprüft wird, was ja auch stimmt - aber dass die "and"-Verknüpufng damit auch verlorengeht ... wäre eigentlich logisch. (Und da es dieselben Ergebnisse lieferte, habe ich gar nicht weiter überlegt.)

Tut mir leid, wenn ich da verschlimmbessere, aber das kleine Genie Eliazz wird sich wohl nicht so leicht verwirren lassen.

Gibt es denn auch eine Möglichkeit, bei einer Array, deren Elemente mit "and" geprüft werden, das in nur einem Schritt zu tun?

[Sirius3]

@BlackJack: »div« teilt das 128bit-Register rdx:rax durch rcx. Siehe auch http://download.intel.com/products/proc ... 253666.pdf Seite 293.
Daher müssen die oberen 64bit null sein. Das Ergebnis liegt dann in rax und der Rest der Division in rdx.

@Gwunderi:

Code: Alles auswählen

if all(a%x>0 for x in prime_proof): ...

[Gwunderi]

Danke für den Code Sirius

Dann geht es doch so (hoffe ich wenigstens, bei den geprüften Zahlen stimmt es mal):
Da man in "primteiler" eine Anfangszahl eingeben muss, habe ich 2 eingesetzt, daher muss man bei einer ungeraden Zahl daran denken, die 2 aus den Lösungen zu streichen.
Nur geht es bei hohen Zahlen (z.B. der von Eliazz) eine halbe Ewigkeit.
Sollte man also noch eine Methode einbauen, dass man bei jeder neu gefundenen Primzahl die Vielfachen davon vor dem neuen Prüfgang aussiebt (wahrscheinlich ist es das, was einige User hier gemeint haben?)

Code: Alles auswählen

primteiler = [2]

n = int(input("Gib eine ganze Zahl ein: "))

a = 3
        
while a <= n/2:
    if all(a%x > 0 for x in primteiler) and n%a == 0:
            primteiler.append(a)
    a = a + 2
print(primteiler)

Habe es mit folgenden Zahlen ausprobiert:
15015 (=3*5*7*11*13)
10010 (=2*5*7*11*13)
60030 (=2*3*5*23*29)
6040 (gibt 2, 5, 151 heraus)

[snafu]

Ich poste jetzt auch einfach mal eine mögliche Python-Lösung, diesmal orientiert an Euklid (was ja eigentlich auch das naheliegendste ist):

Code: Alles auswählen

from itertools import count, takewhile

def get_largest_prime_factor(n):
    if n < 2:
        raise ValueError('n must be >= 2')
    for candidate in takewhile(lambda i: i <= n, count(2)):
        while n % candidate == 0:
            n /= candidate
    return candidate

[Hirschin]

Hallo zusammen,

Habe auch ein paar Anmerkungen:
Will man prüfen, OB eine Zahl n eine Primzahl ist, genügt es, bis zur Wurzel von n zu prüfen.
Aber um die grösste Primzahl, die Teiler von n ist herauszufinden genügt es nicht, habe ich eben herausgefunden.
Nehmen wir z.B. 33 - ist 33 eine Primzahl? da genügt es, bis 6 zu prüfen, denn 11 * 3 wurde schon bei der 3 geprüft.
Aber die grösste Primzahl, die Teiler von 33 ist - also 11 - würde man hier glatt "übersehen".

Man muss also doch, wie BlackJack anfangs meinte, bis n/2 prüfen!
]

Jaja, lang lang ist es her mit den Primzahlen!
Mit Hilfe der Primfaktorzerlegung wird eine natürliche Zahl in ein Produkt von Primzahlen zerlegt, zum Beispiel ist 24 = 2*2*2*3. Ein Primfaktor muss also zwei Bedingungen erfüllen: Erstens muss ein Primfaktor eine Primzahl sein. 4 kann also kein Primfaktor sein, da sie sich weiter in 2*2 zerlegen lässt. Zweitens muss ein Primfaktor ein Teiler dieser natürlichen Zahl sein. Die Zahl muss also ohne Rest durch den Primfaktor teilbar sein.
(Quelle:http://primfaktorzerlegung.net/)