Frage von Kyraxan, 92

Wie kann man in Excel die 10001. Primzahl herausfinden?

Hallo ich würde gerne in Excel ne Liste erstellen wo ich die Primzahlen von 1-10001 in schnelle auflisten kann. Gibt es eine Funktion dafür oder was anderes. (Bitte keine vorgefertigten Listen aus dem Internet)

Hilfreichste Antwort - ausgezeichnet vom Fragesteller
von Iamiam, Community-Experte für Excel, 47

Mit dieserr Fkt kannst Du jede Zahl drauf testen:

Function PrimZahlKetteStd(Zahl As Range)  'funktioniert auch mit sehr großen Zahlen ausreichend schnell (10^15, dann merklich langsamer)
Dim i, Kette, Quo, Start: Start = Time 'Start nicht essentiell, dient zur Zeitanzeige ---auch Quo ü'flüssig, könnte auch mit Zahl weiterrechnen
Quo = Zahl: Debug.Print Zahl.Address(external:=True) & " = " & Quo & " Start:" & Now() '---nicht essentiell---
For i = 2 To Int(Zahl ^ 0.5)
nochmal:
If Int(Quo / i) = Quo / i Then Quo = Quo / i: Kette = Kette & "*" & i: Debug.Print Quo & " " & Kette: GoTo nochmal
Next i '______________________________________________________________- î nicht essentiell!---------------------- ____________
If Quo > 1 Then
PrimZahlKetteStd = Mid(Kette, 2, 999) & "*#" & Format(Quo, "#,##0") & " # ist Primzahl > Wurzel(" & Zahl.Address & ")! (" & Round((Time - Start) * 24 * 60 * 60, 0) & "sec)"
Else '________________________________________________________________________________________________ î nicht essentiell!-----------------------------------
PrimZahlKetteStd = Mid(Kette, 2, 999)
End If: Debug.Print Now() & " Diff=" & Round((Time - Start) * 24 * 60 * 60, 0) & "sec)" 'nicht essentiell
End Function 'getestet:123456789101112000 => 2*2*2*2*2*2*3*5*5*5*2437*#2110805449 # ist Primzahl > Wurzel (96 sec)

Die Liste hast Du ja schon mit dem µ von Subopt erstellen können. Hier noch meine Variante (Vorlage siehe Kopf):

'zur Frage www.gutefrage.net/frage/primzahlen-exel       Lösung aus:
'http://www.eggheadcafe.com/microsoft/Excel/33491515/primzahlen--excel-2003.aspx runterblättern
Public Sub Primzahlen() 'extrem schnelle Primzahlauflistung (60.000, bis 746.773 )
Const pMax As Long = 821641 'höchste zu berechnende Zahl für 65536 Zellen. Größenfestlegung sofort bei Definition!
Dim p(pMax) As Boolean 'Hilfs-Array
Dim x(65536, 1) As Long 'Primzahlen-Array 'Setzungen:
Dim lngX As Long, lngP As Long, lngI As Long: lngX = 0: lngP = 1
Do
lngX = lngX + 1
Do
lngP = lngP + 1
Loop Until Not p(lngP) '
For lngI = lngP To UBound(p()) Step lngP 'UBound(p()) = höchster=(?)=letzter Wert der Matrix p(pMax = lngP)?
p(lngI) = True
Next lngI
x(lngX, 1) = lngP
Loop Until lngX = 65536
Range("A1:A65536") = x
End Sub

geht noch für xl bis 2003, läuft aber auch in neueren Versionen

esetzt Du 65536 durch 1048576, sollte es auch die Möglichkeiten von xlsm auszureizen gestatten (wobei mit komplizierteren Algorithmen sicher auch in xl noch mehr möglich wäre, aber wer braucht's schon?

Kommentar von Iamiam ,

Hab vergessen:

Vorsicht! Das Makro überschreibt alles in Spalte A !

also ggf vorher eine neue Spalte A einfügen!

Kommentar von Iamiam ,

Hab noch was wichtiges vergessen: am Modulkopf:

Option Explicit: Option Base 1

unbedingt zumindest das Zweite: Option Base 1

Kommentar von Iamiam ,

Danke für den *, schließe daraus, dass du es hinbekommen und erfolgreich getestet hast!

(die 10001. ist natürlich die in Zeile 10001 ggf +/- 1, wo die erste steht.

Expertenantwort
von Suboptimierer, Community-Experte für Excel, 36

Ich habe mir mal ein Makro geschrieben. Der Aufruf ist dann dazu:

=PERSONAL.XLSB!istprimfermat(ZEILE())

Die Anzahl erhältst du mit 

=ZÄHLENWENN(primbereich;WAHR)

Das Makro:

Function ISTPRIMFERMAT(ByVal iZuTestendeZahl As Long) As Boolean
  'Führt auf eine Zahl den Fermatschen Primzahltest durch und gibt
  ' zurück, ob der Test bestanden wurde.
  ' Es werden die Basen 2, 3, 5 und 7 getestet
  ' 03.11.2015 TH

Dim a As Long ISTPRIMFERMAT = True
Select Case iZuTestendeZahl Case 2, 3, 5, 7: Exit Function End Select
If iZuTestendeZahl <= 7 Then ISTPRIMFERMAT = False Exit Function End If
a = 2 While a <= 7 If iZuTestendeZahl Mod a = 0 Then ISTPRIMFERMAT = False Exit Function Else If aHochmModn(a, iZuTestendeZahl - 1, iZuTestendeZahl) <> 1 Then ISTPRIMFERMAT = False Exit Function End If End If
If a <> 2 Then a = a + 1 a = a + 1 Wend End Function
Kommentar von Suboptimierer ,

Als Excelformel habe ich mir Folgendes überlegt:

=PRODUKT((REST(ZEILE();ZEILE(INDIREKT("$2:$"&ABRUNDEN(ZEILE()/2;0))))<>0)+(ZEILE()=2))

Das ist eine Matrixformel, deren Eingabe mit Strg + Shift + Enter abgeschlossen werden muss. 

Diese Formel kannst du dann ab Zeile 2 starten lassen und einfach über das Kopierkreuz nach unten ziehen.

1 bedeutet prim, 0 nicht prim. Mit WENN könntest du das Resultat noch auf textuelle Begriffe münzen.

Kommentar von Suboptimierer ,

Anm.: Die 3 muss noch abgefangen wwerden → +(ZEILE()=3) 

Am Ende auf > 0 dann abprüfen, um einen boolschen Wert zu erhalten.

Kommentar von Suboptimierer ,

Das Sieb des Eratosthenes würde dann so funktionieren:

A3: 1
A4: 2
A5: 3
...
D3: FALSCH
D4: WAHR
D5: =PRODUKT(WENN($D$4:D4;REST(A5;$A$4:A4*$D$4:D4)))>0
...

Und herunterziehen.

Leider scheint das die Rechenkapazität von Excel 2010 schon ab n=953 zu überlasten, obwohl eigentlich weniger Operationen durchgeführt werden müssten, als bei der anderen PRODUKT-Formel von oben.

Kommentar von Suboptimierer ,

Es gab zwar keine Beschwerde (was mich wundert), aber es fehlt die Definition von aHochmModn, welche ich der Vollständigkeit halber nachreiche.

Private Function aHochmModn(ByVal a, m, n As Long) As Long
  aHochmModn = 1
  While m <> 0
    If m Mod 2 = 0 Then
      a = (a * a) Mod n
      m = m / 2 ' Typ Long!
    Else
      m = m - 1
      aHochmModn = (aHochmModn * a) Mod n
    End If
  Wend
End Function
Antwort
von dkilli, 41

Schau hier:

http://www.excelformeln.de/formeln.html?welcher=129

Kommentar von Iamiam ,

ergänzt als Einzelabfrage meine Makroformel sehr schön, da eben KEIN Makro und somit als xlsx speicherbar!

Kommentar von dkilli ,

Das stimmt.

Die Adresse ist ausgezeichnet

http://www.excelformeln.de/

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten