www.jammni.de

Gepostet:
02.11.2008 17:42

Primfaktorenzerlegung von 2 Zahlen

Hi...
Also ich soll ein Programm programmieren, dass aus zwei natürlichen Zahl n und m (n <= 2, m <= 2) die Primzahlen wiedergibt die beide Zahlen enthalten und diese sollen aufsteigend
georndet sein. Bsp: primfaktor 51 306 ergibt [3,17]

Ich habe ja hier schon ein programm gefunden das die Primzahlen von einer Zahl wiedergibt, aber vielleicht kann man sowas auch bei 2 Zahlen machen. Man könnte es ja so lösen dass es von beiden Zahlen die Primzahlen ermittelt und dann eine Abfrage welche Zahlen gleich sind. Wenn es eine elegantere Lösung gibt würde ich mich darüber freuen.

Danke

Zum Seitenanfang

ICQ

Siracusa

Gepostet:
02.11.2008 20:50

Hallo,

wenn du eine Funktion isPrime hast, die entscheidet, ob eine Zahl eine Primzahl ist, dann könntest du es so machen: Du gehst alle Zahlen x von 2 bis zum Maximum von n und m durch. Wenn x eine Primzahl ist und ein Teiler von n und von m, dann packst du x in die Ergebnisliste, sonst gehtst du eine Zahl weiter. Es würde auch reichen alle Primzahlen bis zum Maximum von n und m durchzugehen, falls du eine Funktion hättest, die dir alle Primzahlen effizient berechnet.

Eine andere Möglichkeit wäre, zunächst den ggT von n und m zu berechnen und dann nur diese Zahl in Primfaktoren zu zerlegen. Falls ggT(n,m) = 1, dann ist die Ergebnisliste leer, denn dann haben beide Zahlen keine gemeinsamen Primfaktoren.

Viele Grüße,

Siracusa

Zum Seitenanfang

TeamBob

Gepostet:
03.11.2008 11:46

hallo

Also bei mir sieht es so aus... wie du unten gesagt hattest

ggT :: Int -> Int -> Int
ggT a b
| a > b = ggT (a-b) b
| a < b = ggT a (b-a)
| otherwise = a

factors :: Int -> [Int]
factors n = [x | x <- [1..n], n `mod` x == 0]
prime :: Int -> Bool
prime n = factors n == [1,n]
primFaktoren :: Int -> [Int]
primFaktoren n = [x | x<-factors n, prime x]

wo soll ich den unten das ggT ersetzen

Zum Seitenanfang

ICQ

Siracusa

Gepostet:
08.11.2008 04:57

Hallo,

etwa so (ungetestet):

gemeinsameFaktoren :: Int -> Int -> [Int]
gemeinsameFaktoren x y =
  | t == 1    = []
  | otherwise = primFaktoren t
  where
    t = ggT x y

Mal testen und ggf. anpassen.

Viele Grüße,

Siracusa

Zum Seitenanfang

Haskell-Forum