Ein Teiler einer Zahl

Badestrand

Hi!

Ich hätte mal eine Frage Und zwar hab ich eine ziemlich große Zahl (>2 Mio Stellen), kann man davon auf eine einfache Art und Weise einen (größeren) Teiler rausfinden, so dass kein Rest übrig bleibt?

Und dauert es lange, von so einer großen Zahl die Wurzel zu ziehen? Und kann man von einer Wurzel leicht den "Rest" rausbekommen, so wie modulo beim dividieren?

ghorst

wie hast du denn deine 2mio stellen gespeichert?
oder anders hast du tatsächlich 2mio stellen oder nur eine fließkommazahl, die in der größenordnung liegt?

Daniel E.

Interessant wäre auch zu wissen, ob sich die Zahl nach einem bestimmten Schema zusammensetzt (Produkt von großen Primzahlen oder so).

Ansonsten ist die einfältige Strategie, einfach die Zahl von unten weg mit allen Primzahlen auf Teilbarkeit zu prüfen, gar nicht mal so schlecht (50% der zufällig gewählten Zahlen brauchen nur einen Vergleich).

Badestrand

ghorst schrieb:

wie hast du denn deine 2mio stellen gespeichert?
oder anders hast du tatsächlich 2mio stellen oder nur eine fließkommazahl, die in der größenordnung liegt?

Bis jetzt hab ich sie noch gar nicht gespeichert, ist erstmal nur hypothetisch, ich will's noch nicht implementieren, wenn ich noch nicht weiß, wie Die Zahl setzt sich aus einer Datei zusammen, ich öffne also eine beliebige Datei und interpretiere den Byte-Strom als riesige Integer-Zahl

Daniel E. schrieb:

Interessant wäre auch zu wissen, ob sich die Zahl nach einem bestimmten Schema zusammensetzt (Produkt von großen Primzahlen oder so).

Ne, is leider zufällig

Daniel E. schrieb:

Ansonsten ist die einfältige Strategie, einfach die Zahl von unten weg mit allen Primzahlen auf Teilbarkeit zu prüfen, gar nicht mal so schlecht (50% der zufällig gewählten Zahlen brauchen nur einen Vergleich).

Also einfach von 1 über 3 bis so weit es geht? Oder anders herum?

Und wie ist das mit der Wurzel? Mit "Rest" meinte ich übrigens sowas: Bei einer Zahl von 123 wäre die Wurzel 11 mit Rest 2.
Aber danke schon mal für die Antworten!

borg

Badestrand schrieb:

Und wie ist das mit der Wurzel? Mit "Rest" meinte ich übrigens sowas: Bei einer Zahl von 123 wäre die Wurzel 11 mit Rest 2.
Aber danke schon mal für die Antworten!

einfach die wurzel bis auf eine nachkommastelle bestimmen, nach unten runden, quadrieren und rest bestimmen. sollte hinreichend schnell sein.

das mit den teilern hängt ganz davon ab wieviele primteiler die zahl hat.

Badestrand

Na gut, noch eine Frage:

Kann man für eine Folge (nicht so lang :D) aus 0en und 1en mehr oder weniger leicht (oder überhaupt?) eine Funktion bestimmen, die diese beschreibt?

Walli

Badestrand schrieb:

Daniel E. schrieb:

Ansonsten ist die einfältige Strategie, einfach die Zahl von unten weg mit allen Primzahlen auf Teilbarkeit zu prüfen, gar nicht mal so schlecht (50% der zufällig gewählten Zahlen brauchen nur einen Vergleich).

Also einfach von 1 über 3 bis so weit es geht? Oder anders herum?

Die Teilbarkeit auf 1 kannste Dir schonmal sparen. Ist ausserdem nicht prim .

Christoph

Badestrand schrieb:

Na gut, noch eine Frage:

Kann man für eine Folge (nicht so lang :D) aus 0en und 1en mehr oder weniger leicht (oder überhaupt?) eine Funktion bestimmen, die diese beschreibt?

Klar:

char f(unsigned int n) {
  const char* number = "11111010111";
  if(n < strlen(number))
    number[n];
  else
    return '0';
}

Aber das ist bestimmt nicht Sinn der Sache.
Du musst dir zuerst überlegen, was für eine Art Funktion du erwartest. Wenn du zum Beispiele ein Polynom erwartest, musst du die entsprechenden linearen Gleichungssysteme aufstellen und lösen.

CStoll

Badestrand schrieb:

Ich hätte mal eine Frage Und zwar hab ich eine ziemlich große Zahl (>2 Mio Stellen), kann man davon auf eine einfache Art und Weise einen (größeren) Teiler rausfinden, so dass kein Rest übrig bleibt?

Wenn du das schaffen würdest, wärst du der Star - die meisten modernen Verschlüsselungssystem basieren auf der Annahme, daß man die Teiler einer natürlichen Zahl nicht in absehbarer Zeit ermitteln kann (Faktorisierung).

Badestrand

Dann würde ich ja einige Verschlüsselungen knacken Lass ich das lieber mal , Sicherheit geht vor

CStoll

Badestrand schrieb:

Dann würde ich ja einige Verschlüsselungen knacken Lass ich das lieber mal , Sicherheit geht vor

Ach, mach nur - und wenn du schon dabei bist, kannst du auch gleich das P-NP-Problem lösen