Hier ein bisschen Feedback/Wüsche:
Erstmal hast du zwar ohne Kommentare programmiert, aber auch ohne C Kenntnisse konnte ich die Idee deines Skriptes ganz gut nachvollziehen.
(Selbst wenn ich das Sieb des Eratosthenes nicht bereits gekannt hätte)
Ich bin zwar keineswegs mit C vertraut, aber dein Sieb des Eratosthenes hätte doch auch in einer Liste von Wahrheitswerten implementiert werden können und dadurch einen kleinen Geschwindigkeitsboost bekommen können, oder?
Als Erweiterung könntest du ja die Liste in k viele Teile teilen, die von k Threads bei jedem "Sieben" je ein Stück aktualisieren.
Ich habe den Code zwar nicht getestet, war aber von dem Titel angetan (...), da ich aber keine Liste aller Primzahlen von 2 bis n brauche und von C so gut wie keine Ahnung habe,
würde ich dich um folgendes Features bitten:
Eine Funktion IsPrime(x) : boolean, die auf Primzahlen prüft.
D.h. man kann eine beliebige natürliche Zahl auf ihre Primzahleneigenschaft prüfen. Dazu fallen mir spontan 2 Verfahren ein:
AKS-Primzahltest (nicht probabilistisch soweit ich weiß und daher hilfreich für mich)
Miller Rabin Test (probabilistisch)
*weitere, möglichst effiziente(re) Verfahren die nicht probabilistisch sind fänd ich auch gut*
Der naive Ansatz die Zahl x auf alle Teiler < WurzelAus(x) dauert viel zu lange, wenn die Primzahl ca. 100 Stellig (<=>10^100) ist.
Ich würde es Klasse finden, wenn du das mal in C probieren könntest 
doch auch in einer Liste von Wahrheitswerten implementiert werden können und dadurch einen kleinen Geschwindigkeitsboost bekommen können, oder?
Das Problem ist das c kein Boolean an sich als datentyp hat.
Nur von MS z.b. die Definition.
in C++ schon.
Hehe 
Oder einfach so:
AutoIt
Func IsPrime($x)
If Not IsNumber($x) Then Return False
If $x < 2 Then Return False
If $x - Int($x) Then Return False
For $i = 2 To $x -1
If Not Mod($x, $i) Then Return False
Next
Return True
EndFunc
C++
bool IsPrime(unsigned long long x) {
if (x < 2) {return false;}
for (unsigned long long i = 2; i < x -1; i++) {
if (!(x % i)) {return false;}
} return true;
}Jede Zahl von 2 bis x einfach mit der Funktion prüfen und schon hat man seine Primzahl. Dauert aber demnach auch länger... 
Jede Zahl von 2 bis x einfach mit der Funktion prüfen und schon hat man seine Primzahl. Dauert aber demnach auch länger...
Von 2 bis Ceiling(Sqrt(x)) würde auch reichen.
Kannst du mir das bitte näher erläutern?
Da kann ich mir gerade nichts zu erschließen
Kannst du mir das bitte näher erläutern?
Ok, nehmen wir als Beispiel 40. Die Grenze wäre in diesem Fall 7.
40 / 8 = 5 R 0 ; brauchst du aber nicht überprüfen, da du die 5 schon überprüft hast
40 / 10 = 4 R 0 ; brauchst du auch nicht überprüfen, da du die 4 schon überprüft hast
40 / 20 = 2 R 0 ; brauchst du auch nicht überprüfen, da du die 2 schon überprüft hast
...
Man könnte also sagen, dass sich die Überprüfungen an der Grenze spiegeln. Ist nicht gerade gut erklärt aber ich hoffe du verstehst was ich meine.
Ah
Okey, danke James
Daran habe ich nicht gedacht :x
Außerdem muss man nur alle kleineren Primzahlen in dem Bereich überprüfen
Hi,
zunächst: ich war total stolz den o.a. Code in VC++ mit kleinen Änderungen zum Laufen (und compiliert) bekommen zu haben^^
Was soll man sagen...C halt...der Code ist 4x langsamer als mein unoptimiertes Assemblerstück, dass sogar noch sämtliche Primzahlen in eine Datei schreibt...
Mit einem (so wie hier beschrieben) modifizierten Sieb ist nochmal Faktor 3-4 in der Geschwindigkeit drin...
Btw. früher gab es mal den µ-It (auch als light-Version) hier im Forum, um Primzahlen und Scripte ging es im angehängten Link, viel wichtiger sind die vorgestellten Algorithmen, die entsprechend umgesetzt Welten schneller in einer Compilersprache laufen http://www.autoit.de/index.php?page=Thread&postID=141580#post141580
Andy, guter Code
Sie können darum bitten, den gleichen Code zu erstellen, um die Zahl in Primfaktoren zu verteilen
1232334646758235345 ==> 5*13*2131*1942141*4580903
948013690567935577 ==> 948013690567935577
Oder so prüfen:
Alina, Warum zeigst du mir das - dein Code funktioniert nicht mit großen Zahlen
EDIT BugFix: [Link entfernt]
#include <GMP.au3>
$sNumber='7449127220995854990111634981969667504202586690187189283949036813312551732826094712426142869403456819'
$iYes=__IsPrime_GMP($sNumber)
MsgBox(4096,'$iYes','&$iYes&)
Func __IsPrime_GMP($n)
Return StringInStr($n,'.')?-1:(StringCompare($n,_GMP_Next_Prime(_GMP_SubInteger($n,1)))?0:1)
EndFunc
Func _GMP_Next_Prime($sValue)
Local $t_Value=DllStructCreate($tag_mpz_t),$p_Value=DllStructGetPtr($t_Value)
_GMPz_Init_Set_Str($p_Value,$sValue)
_GMPz_NextPrime($p_Value,$p_Value)
$sRes=_GMPz_get_Str($p_Value)
_GMPz_Clear($p_Value)
Return $sRes
EndFunc
Func _GMPz_NextPrime($pResult,$pVal)
DllCall($hDLL_GMP,'none:cdecl','__gmpz_nextprime','ptr',$pResult,'ptr',$pVal)
EndFuncOr GMP "__gmpz_probab_prime_p"
Die Frage war, wie man für große Zahlen
1232334646758235345 ==> 5*13*2131*1942141*4580903
948013690567935577 ==> 948013690567935577
Aber für große Zahlen funktioniert es nicht.
Func GetFactors($nVal)
Local $sText, $X = 3
while IsInt($nVal / 2) And $nVal > 3
$nVal /= 2
$sText &= "*2"
WEnd
While $X*$X <= $nVal
If IsInt($nVal / $X) Then
$nVal /= $X
$sText &= "*" & $X
Else
$X += 2
EndIf
WEnd
return StringMid($sText & "*" & $nVal, 2)
EndFuncFolgendes habe ich aus einem Uni-Bereich rausgezogen.
n < 1.373.653 : es genügt, a= 2 und 3 zu testen,
n < 9.080.191 : es genügt, a = 31 und 73 zu testen,
n < 4.759.123.141 : es genügt, a = 2, 7, und 61 zu testen,
n < 2.152.302.898.747 : es genügt, a = 2, 3, 5, 7, und 11 zu testen,
n < 3.474.749.660.383 : es genügt, a = 2, 3, 5, 7, 11, und 13 zu testen,
n < 341.550.071.728.321 : es genügt, a = 2, 3, 5, 7, 11, 13, und 17 zu testen.
n < 3.825.123.056.546.413.051 : es genügt, a = 2, 3, 5, 7, 11, 13, 17, 19, und 23 zu testen.
n < 318.665.857.834.031.151.167.461 : es genügt, a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 zu testen.
Dabei dürfen nur solche n getestet werden, die größer sind als das jeweils größte a !!