Zahl zu Primfaktor finden

Ook! · Apr 26, 2009

Hallo!

ich überlege gerade, wie ich die größte Zahl zu einem gegebenen Primfaktor finden kann...

Das soll so aussehen, dass das Limit und der größte Primfaktor vorgegeben sind.
Nun soll bis zum Limit die größte Zahl gefunden werden, die diesen Primfaktor als ihren größten besitzt.
Soll auch mit wirklich großen Zahlen funktionieren...

Beispiele:
Limit: 10**6
Primfaktor: 347
Größte Zahl: 999707 [43, 67, 347]

Limit: 10**18
Primfaktor: 257
Größte Zahl: <n>

Wie würdet Ihr das umsetzen?

Gruß
Felix

Eydeet · Apr 26, 2009

Ich würde das so machen:
Faktor = abrunden(Limit / Primfaktor)

also bei deinem ersten Beispiel:

Faktor = abrunden(10**6 / 347) = abrunden(2881,844...) = 2881
2881 * 347 = 999707

Zweites Beispiel in Python:
print int(10**18 / 257) * 257
> 999999999999999859

ThePhil · Apr 26, 2009

Hi, dabei könnten aber auch Zahlen rauskommen, die größere Primfaktoren haben, als den gesuchten, und er wollte ja:

die größte Zahl gefunden werden, die diesen Primfaktor als ihren größten besitzt.

im zweiten beispiel hat 999999999999999859 den primfaktor 4624149349, der größer ist als 257, und demnach ist 257 nicht deren größter.

Aber mir fällt grad auch kein anderer weg ein, als von dieser zahl (999999999999999859) die nächstkleinere zu suchen, deren primfaktoren klein gunug sind, was glaub ich ne ziemlich schlechte laufzeit hat.

mfg ThePhil

Elderan · Apr 26, 2009

Hallo,
Eydeet Ansatz ist gar nicht so schlecht.

Die Zahl floor(10**18 / 257) kann man dann in die Primfaktoren zerlegen lassen und sich den Größten betrachten.
Sollte dieser größer sein als 257, zerlegt man floor(10**18 / 257)-1 in Primfaktoren und betrachtet den größten Primfaktor usw.

Da man bei einem Primfaktor >257 abbrechen kann, sollte dies eigentlich relativ schnell gehen, da man die Primfaktoren bis 257 sehr schnell aus dem Ergebnis dividieren kann.

Einfach eine Liste mit den Primzahlen bis 257 erstellen lassen, diese in einer Schleife ablaufen lassen:

Code:

tmp = floor(10**18 / 257)-1;
i = 0;
primzahl = primzahlen[i]; //Primzahlen bis 257
while(tmp > primzahl && i < count(primzahlen)) {
  if(tmp % primzahl == 0)
       tmp /= primzahl;
  else
     primzahl = primzahl[i++];
}
//Testen ob tmp > (oder >=) 257 ist

Ook! · Apr 27, 2009

Also so wie ich es jetzt probiert habe, komme ich auf keinen grünen Zweig...
Mag jemand noch einmal genauer erklären, wie das funktionieren soll?

EDIT:
Habs nun doch selber gebacken bekommen...

EDIT 2:
... oder wohl doch nicht, hehe =))

Elderan · Apr 27, 2009

Hallo,
ich hab doch den Algorithmus halbwegs skizziert:

Code:

k = 0;
zahl =   floor(10**18 / 257);


while(true) {
  i  = 0;
  primzahl = primzahlen[i]; //Primzahlen 2 bis 257
  tmp = zahl;
  while(tmp > primzahl && i < count(primzahlen)) {

    if( tmp % primzahl == 0)
       tmp /= primzahl;
    else {
       i++;
       if(i < count(primzahlen)) //Nur um Überläufe zu verhindern
         primzahl = primzahlen[i];
    }
  }
  if(tmp >= 257) //Evt. hier >, je nachdem was man möchte
     zahl--;
  else
    break;
}

// zahl sollte nun die größte Zahl enthalten

Das sollte soweit hoffentlich klappen. Ansonsten wo hackt es denn noch?

Edit:
Natürlich enthält 'zahl' die größte Zahl

ThePhil · Apr 27, 2009

also der ansatz klingt gar nciht so schlecht, wenn deine primzahl klein ist.

1. du teilst deine ausgangszahl durch deine primzahl und rundest ab, sagen, wir das ergebnis ist x

2. du hast ein primzahl array mit allen primzahlen von 2 bis [primzahl]
2.1. du gehst das array von der 2 an durch, und teilst solange durch die array-primzahl, wie es halt geht
2.2 du hörst auf, wenn bei irgendeiner teilung 1 rausgekommen ist, oder:
2.3 du hörst auf, wenn du oft genug durch die letzte primzahl geteilt hast, wenn jetzt das geteilte immer noch größer als 1 ist, ist x durch eine größere primzahl teilbar kommt also für dich nciht in frage

3. du versuchst x-1 und gehst damit wieder durch 2., bis 2.2 erfüllt ist

Sollte funktionieren, über die laufzeit: bin ich immer noch skeptisch, aber probiers mal aus

Mfg ThePhil

Edit: Elderan war schneller, zu zeile 25: du meinst sicher zahl sollte die größte zahl sein

Ook! · Apr 27, 2009

Hi,

ich habe den Ansatz auch so umgesetzt (beim ersten Versuch - nun durch deinen ersetzt), nur bekomme ich 'scheinbar' falsche Ergebnisse...
Also bisher habe ich es so umgesetzt:

Code:

int[] primzahlen = new int[] {2,3,5,...,241,251,257};
int primzahl = primzahlen[0];
		
long zahl = (long) Math.floor(Math.pow(10, 18) / 257);
long tmp = zahl;
while (true) {
	int i = 0;
	primzahl = primzahlen[i];
	tmp = zahl;
	while (tmp > primzahl && i < primzahlen.length) {
		if (tmp % primzahl == 0)
			tmp /= primzahl;
		else {
			i++;
			if (i < primzahlen.length)
				primzahl = primzahlen[i];
		}
	}
	if (tmp >= 257)
		break;
	else
		zahl--;
}
System.out.println(zahl +" "+ Arrays.toString(factors(zahl)));

Und gab mir als Ergebnis:
3891050583657587
[7, 120209, 4624149349]

ThePhil · Apr 27, 2009

Hi, es funktioniert nicht, weil die abbruchbedingung falsch ist.

Code:

if (tmp >= 257) 		
break; 	
else 		
zahl--;

wenn tmp größer als 257 ist, hat die zahl nämlich größere primfaktoren, und du musst zahl um eins verringern, im anderen fall bist du fertig.
also:

Code:

if (tmp >= 257) 		
zahl--;
else 		
break;

(nicht wirklich getestet, da ich grad kein so großes primzahlen array habe)
Mfg ThePhil

Ook! · Apr 27, 2009

Das war schonmal ein weiterer Schritt zum Ziel =)
.. jedoch noch nicht das Ziel!

Code:

3891050583501735 [3, 3, 5, 41, 61, 73, 97, 137, 157, 227]

ThePhil · Apr 27, 2009

ok,
ich bin mir zwar sicher, das du auf den letzten schritt selber kommen würdest, aber du musst das ergebnis noch mal mit der primzahl, mit 257, multiplizieren, dann kommt 999999999959945895 raus.
Mfg ThePhil

Ook! · Apr 27, 2009

mhh.... also irgendwann durch ausprobieren bestimmt

Danke =)

Lesco · Apr 28, 2009

Der Algorithmus funktioniert nicht, wenn die gesuchte Zahl den gewünschten Faktor mehrmals enthält. Z.B 257^3 ist nach dem rausdividieren der Faktoren und dem Teilen zu Beginn immer noch 257^2 und somit >257. Daher müsste man jeweils noch so oft wie möglich durch den Faktor dividieren.
Hier eine korrigierte Version:

Code:

import java.util.*;

public class Bftest {
    static final int fac = 257;
    public static void main(String[] args) {
	int[] primzahlen = new int[] {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251};
	int primzahl = primzahlen[0];
	long zahl = (long) Math.floor(Math.pow(10,18) / fac);
	long tmp = zahl;
	while (true) {
	    int i = 0;
	    primzahl = primzahlen[i];
	    tmp = zahl;
	    while (tmp > primzahl && i < primzahlen.length) {
		if (tmp % primzahl == 0)
		    tmp /= primzahl;
		else {
		    i++;
		    if (i < primzahlen.length)
			primzahl = primzahlen[i];
		}
	    }
	    while(tmp % fac == 0)
		tmp /= fac;
	    if (tmp > fac)
		zahl--;
	    else 
		break;
	}
	zahl *= fac;
	System.out.println(zahl +" ");
    }
}