Office: Primzahlen?? Hilfe!!

Also ich habe jetzt eine Funktion gemacht mit der ich Primzahlen ermitteln kann und ich gehe mal davon aus, dass sie stimmt...(siehe weiter unten...)
Mein eigentliches problem ist, wie kann ich die Funktion Prim() beschleunigen, indem nicht so viel unnütz gesucht wird?
Muss bei der Untersuchung, ob 197 eine Primzahl ist, wirklich getestet werden, ob 196 ein Teiler ist?
Wie groß kann der größte echte Teiler denn höchstens sein?
Kann vielleicht noch ein bisschen „früher“ festgestellt werden, dass es gar keinen echten Teiler gibt und die Zahl daher eine Primzahl ist?

Code:

 

Moin, anfänger_engel,

vielleicht solltest Du Dir zur Vorgehensweise Ermittlung von Primzahlen (Verdoppelung der Einfach-Formel) ansehen...

 

Hallo!

Die geänderten Stellen im Code sind fett markiert! Code:

 

HAllo

Du brauchst nur bis zur Ganzzahl der Wurzel zu testen.

Dies hier habe ich vor einiger Zeit mal gebastelt.
Schau es dir mal in aller Ruhe an...

' **********************************************************************
' Modul: prim Typ: Allgemeines Modul
' **********************************************************************

Option Explicit

Public Function primzahltest(zahl) As Boolean
Dim wurzel
Dim L
Dim bol As Boolean
bol = True
wurzel = Int(Sqr(zahl))
For L = 2 To wurzel
If (zahl / L) = Int(zahl / L) Then
bol = False
Exit For
End If
Next
primzahltest = bol
End Function

Function primfaktoren(zahl) As String
Dim dummy As String
Dim test As Double
Dim wurzel As Double
Dim pruefen
test = zahl
wurzel = WorksheetFunction.Power(zahl, 0.5)
While primzahltest(test) = False
For pruefen = 2 To wurzel
If (test / pruefen) = Int(test / pruefen) Then
dummy = dummy & pruefen & " * "
test = test / pruefen
wurzel = Sqr(test)
Exit For
End If
Next
Wend
dummy = dummy & test
primfaktoren = "=" & dummy
End Function


Der Aufruf in einer Tabelle geht dann so:
Tabelle1

	A	B	C
5	123456	FALSCH	=2 * 2 * 2 * 2 * 2 * 2 * 3 * 643

Zelle	Formel
B5	=primzahltest(A5)
C5	=primfaktoren(A5)

Excel Tabellen im Web darstellen >>

 

Hallo,

Zahlen die größer als die Hälfte der zu prüfenden Zahl sind können keine Teiler dieser Zahl sein, daher
Code:

 

Hi Engel,

im Grunde genommen genügen max. 10 Durchläufe, da jede Zahl, egal wir groß, sofern sie keine Primzahl ist, durch eine dieser Zahlen teilbar ist. Hier ein Bsp.:

Code:

 

HAllo RJ

Hm...
Das stimmt so nicht.
Teste mit deinem Code z.B. mal die 121 oder die 391.

ransi

 

Hallo!

Bei nochmaligem Nachdenken und wälzen alter Studiumsunterlagen komme ich nun zu folgendem Code: Code:

Wie hier schon erwähnt reicht sogar eine Schleife bis zur Ganzzahl der Wurzel. Dann benötigt man nicht einmal alle Werte.

Viele Grüße
rastrans

 

1. du brachst nur bis zur Wurzel der Zahl testen
2. du brachst nur auf Primzahlen testen
d.h. wenn du eine große Zahl z.B. durch 11 (eine Primzahl) versucht hast zu teilen, dann brauchst du 22, 33, 44, .. nicht mehr testen.

ich könnte dir in C# einen sehr, sehr schnellen Algorithmus schicken

Die Voraussetzung für schnelles Finden von Primzahlen ist also eine entsprechend große Liste von schon bekannten Primzahlen.

Ähnlich wie bei der Berechnung der Fakultät einer Zahl.

 

HAllo

Wie schnell ??

ransi

 

Grüezi zusammen

Der folgenden Lösung liegt der Gedanke der Primzahlen-Liste zugrunde - sinnvollerweise würde diese einmalig zu Beginn angelegt und dann bloss noch durchsucht. Ansonsten würde jeder Aufruf der Funktion aus dem Tabellenblatt ein eigenes Array anlegen, was dem Speicher wohl bald den Garaus machen wird.

Code:

 

Ok, dein Code ist dann, wenn dein Speicher ausreichend ist, schneller. Aber erst, wenn du genügend Zeit hattest dein Array aufzubauen.

Mit der größtmöglichen Zahl für den Datentype Long (+2.147.483.647) finde ich meine Funktion aus #8 auch zeitmäßig völlig ausreichend!