Zahlen für ggT generieren?

jackie05 · Beiträge: 357

Hallo,
ich habe bei mir im Programm eine Funktion eingebaut, mit dem ich ggT berechnen kann, aber der Computer generiert mir oft Zahlen, indem der größte gemeinsame Teiler 1 ist und das ist dof.
Wie kann ich die Zahlen so generieren, das der größte gemeinsame Teiler > wie 1 ist?

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:

function ggT(a, b: Integer): Integer;
begin
  if (b > a) then begin  
    Result := a;  
    a := b;  
    b := Result;  
  end;  
  while (b > 0) do begin  
    Result := a mod b;  
    a := b;  
    b := Result;  
  end;  
  Result := a;
end;

procedure NewggT();
begin
  randomize;
  ggTZahlA := random(100)+1;
  ggTZahlB := random(100)+1;
  Form1.lblggT.Caption := 'Bestimme den größten gemeinsamen Teiler von '+IntToStr(ggTZahlA)+' und '+IntToStr(ggTZahlB);
  ggTErgebnis := ggT(ggTZahlA, ggTZahlB);
  Form1.edtggT.Clear;
end;

Ich bedanke mich schonmal im Voraus.

MfG

F34r0fTh3D4rk · Verfasst: Di 31.03.09 16:41

Im einfachsten Fall so:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:

while ggT(a, b) = 1 do
begin
  a := random(100)+1;
  b := random(100)+1;
end;

oder halt nur eine der beiden Zahlen neu generieren (wobei das nicht funktioniert, wenn die andere eine Primzahl ist. Das würde zu einer unschönen Endlosschleife führen

)

mfg

Kha · Verfasst: Di 31.03.09 16:44

jackie05 hat folgendes geschrieben :

Wie kann ich die Zahlen so generieren, das der größte gemeinsame Teiler > wie 1 ist?

Du wählst eine zufällige Zahl c. Wie könntest du nun wohl zu zwei Zahlen a und b kommen, sodass ggT(a, b) (mindestens) c ist

?

_________________
>λ=

jackie05 · Beiträge: 357

Ich bekomme immer Zufallszahlen, indem keine gemeinsame Teiler hineinpassen außer die Zahl 1.

Das möchte ich verbessern, das auch irgendwie Zufallszahlen kommen, indem auch mal eine andere Zahl hineinpasst außer immer nur die 1.

Gibt es dafür vieleich irgendwelche Algorithmus um die Zahlen so zu generieren?
Beispiel:
Bestimme den größten gemeinsamen Teiler von 24 und 60. (12)
Bestimme den größten gemeinsamen Teiler von 12 und 78. (6)
Bestimme den größten gemeinsamen Teiler von 20 und 5. (5)
Bestimme den größten gemeinsamen Teiler von 40 und 65. (5)

und nicht Zahlen wie z.B. diese:
Bestimme den größten gemeinsamen Teiler von 93 und 8. (1)
Bestimme den größten gemeinsamen Teiler von 31 und 22. (1)
Bestimme den größten gemeinsamen Teiler von 8 und 27. (1)
Bestimme den größten gemeinsamen Teiler von 97 und 68. (1)

Danke schonmal.

MfG

jaenicke · Verfasst: Di 31.03.09 18:29

Mach eine Primzahlzerlegung und benutze mindestens einen der Faktoren. Welchen kannst du ja zufällig auswählen.

Ist das für eine bestimmte Anwendung?

F34r0fTh3D4rk · Verfasst: Di 31.03.09 18:32

Ich weiß eigentlich nicht, warum du nochmal nachfragst, du hast doch schon zwei Lösungen bekommen :!:

Wenn sich dir user profile icon

Khas Lösung nicht erschließt, werde ich sie dir nennen:

markieren

Delphi-Quelltext

1:
2:
3:

  s := random(8)+2; 
  a := s * (random(100)+1); // danke jakobwenzel ;)
  b := s * (random(100)+1);

denke das war gemeint

Die beiden Zahlen haben dann auf jedenfall den gemeinsamen Teiler s(>1). In meinem Beispiel sind das die Zahlen 2 bis 9. Statt der 8 kannst du natürlich noch eine andere Zahl auswählen um einen größeren Wertebereich abzudecken.

mfg

jackie05 · Beiträge: 357

Danke Dir.

Ich Programmiere ein Mathematik Programm mit viele verschiedene Rechenoptionen.

Wenn ich z.B. die erste Zahl in Primzahl zerlege z.B.
84 = 1,2,3,4,6,7,12,21,28,42,84
und dann soll ich davon irgendeine Zahl nehmen und beim 2ten Zahl mehrfach mal nehmen Beispiel:
12*8 = 96
ZahlA = 84 ZahlB = 96

der gemeinsame Teiler wäre dann die Zahl 12

So könnte ich es dann machen? oder gibt es noch bessere Wege?

Edit: @F34r0fTh3D4rk Danke Dir, ich werde es mal versuchen.

Vielen Dank für die antworten.

MfG

jakobwenzel · Verfasst: Di 31.03.09 18:48

@

F34r0fTh3D4rk:
Fast:

markieren

Delphi-Quelltext

1:
2:
3:

  s := random(8)+2; 
  a := s * (random(100)+1);
  b := s * (random(100)+1);

_________________
I thought what I'd do was, I'd pretend I was one of those deaf-mutes.

F34r0fTh3D4rk · Verfasst: Di 31.03.09 19:12

aber natürlich, danke

Schande über mich :roll:

JayEff · Beiträge: 2971 Windows Vista Ultimate D7 Enterprise

jackie05 hat folgendes geschrieben :

Wenn ich z.B. die erste Zahl in Primzahl zerlege z.B.
84 = 1,2,3,4,6,7,12,21,28,42,84

Äh, bitte? :shock:

Wo sind denn da Primzahlen ausser 2, 3 und 7?

_________________
>+++[>+++[>++++++++<-]<-]<++++[>++++[>>>+++++++<<<-]<-]<<++
[>++[>++[>>++++<<-]<-]<-]>>>>>++++++++++++++++++.+++++++.>++.-.<<.>>--.<+++++..<+.

jackie05 · Beiträge: 357

JayEff hat folgendes geschrieben :

jackie05 hat folgendes geschrieben :

Wenn ich z.B. die erste Zahl in Primzahl zerlege z.B.
84 = 1,2,3,4,6,7,12,21,28,42,84

Äh, bitte? :shock:

Wo sind denn da Primzahlen ausser 2, 3 und 7?

Ups, Sry, hab da was verwechselt :twisted:

MfG

BenBE · Verfasst: Mi 01.04.09 10:46

Man kann aber auch einfach den Algorithmus für die Berechnung des ggT umkehren und ausgehend von einem gemeinsamen Teiler zufällig zwei Zahlen a und b generieren, die mindestens diesen Teiler aufweisen.

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme