Co-Primzahlen vergleichen

Angenommen, wir haben zwei Zahlen in ihre Primzahlen zerlegt, dargestellt als Listen von (p, d), wobei alle p Primzahlen sind und d die Potenz von p ist.

Gibt es eine Möglichkeit, solche zwei Zahlen zu vergleichen, ohne sie in lange ganze Zahlen umzuwandeln?

Das Vergleichen von zwei Zahlen kann auf das Vergleichen von zwei Co-Primzahlen reduziert werden, aber dann scheint das Glück zu Ende zu gehen, und es scheint, als müsste ich eine Polynomarithmetik durchführen, die der Umwandlung in lange ganze Zahlen entspricht.

Das ist eine wirklich interessante Frage. Ich kann keine Möglichkeit finden, die Primfaktoren von ganzen Zahlen zu verwenden, um den Vergleich mit <, =,> zu beschleunigen.

Hier ist meine Intuition darüber, warum es schwierig sein sollte, Faktorisierung mit <, = und> in Beziehung zu setzen: Bei der Primfaktorisierung geht es um die multiplikative Struktur der ganzen Zahlen, während <und> additive Dinge sind. Vielleicht macht ein Blick auf die Definition von <in der Peano-Arithmetik dies klarer: Die Definition von <wird (unter anderem) durch die folgenden Klauseln gegeben.

1. $\forall x.x < x+1$

2. $\forall xy. x < y \Rightarrow x+1 < y+1$

$x+1$$y+1$$x$$y$$x$$x+1$