funktion um auf primzahl zu testen (zahlengröße 10000stellen und mehr)

Triple-Axe · 30. Mai 2011, 19:00

irgendwie bin ich blind. wenn ich eine 310 stellige zahl auf primzahl testen will geht es nicht
309 stellen geht aber noch

fehler :

System.OverflowException wurde nicht behandelt.
Message=Der Wert für ein Double war zu groß oder zu klein.
Source=Microsoft.VisualBasic

mein button1

VB.NET-Quellcode

Dim test As String = Fast("1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890") '310 stellen

VB.NET-Quellcode

Function Fast(ByVal n As String) As Boolean
'(c) by http://dotnet-snippets.de/dns/effizientere-primzahlpruefung-grosser-zahlen-SID1373.aspx
If n Mod 2 = 0 OrElse n Mod 3 = 0 OrElse n Mod 7 = 0 OrElse n Mod 5 = 0 Then Return False
Dim r As Single = Math.Sqrt(n), f As Short = 11
If r Mod 1 = 0 Then Return False
While f <= r
If n Mod f = 0 OrElse n Mod (f + 2) = 0 Then Return False
f += 6
End While
Return True
End Function

kann mir jemand n tip geben was da falsch ist bzw was ich sonst machen könnte um richtig große zahlen auf prim zu testen

EDIT : modulo ist double also kann es keine 310 stellen

:pinch:

picoflop · 30. Mai 2011, 19:06

Du darfst für sowas sowieso NIE Double nehmen!
Nimm:
msdn.microsoft.com/en-us/library/dd268220.aspx
Gibts allerdings erst ab VB 2010. Wenn du was älteres hast gibts ne BigInt Library auf Codeplex glaube ich ...
biginteger.codeplex.com/
(gibt noch weitere afaik)

Triple-Axe · 30. Mai 2011, 20:49

nene du hast mich falsch verstanden :

If n Mod 2 = 0 OrElse n Mod 3 = 0 OrElse n Mod 7 = 0 OrElse n Mod 5 = 0 Then Return False

DAS

VB.NET-Quellcode

Mod

ist Double

ich werd mal schauen ob ich damit dotnetperls.com/prime was gebastelt bekomm was mit mod ersetzt

ich habe das vb2010 von meinem dad finanziert bekommen also von der seite für alles offen

edit :

c# 2 .net converter spuckt modulo aus developerfusion.com/tools/convert/csharp-to-vb/

Spoiler anzeigen

mal ne doove frage wie prüfe ich ohne MOD / modulo eine division auf rest :?:

edit : wenn das mein mathe lehrer sehen würde der würde mir den hals umdrehen

aber nur unter der bedingung das mich der it ausbilder nicht vorher erwischt

@ wer auch immer das liest : schonmal ne primzahl gebaut ?
wenn ja über 15 stellen ?

kann mir jemand sagen warum ich bei einer 15 stelligen zahl unter 1 sekunde brauche um sie zu generieren und auf prim zu testen und wenn nicht neu generieren zu lassen

aber bei einer 16 stelligen zahl dauert es ca 10 min bei 100% cpu last ?

RodFromGermany · 31. Mai 2011, 09:49

Wenn, dann musst Du Integerdivision verwenden, kein Modulo.
Und Du musst auch nur durch Primzahlen dividieren, um zu testen.

picoflop · 31. Mai 2011, 14:00

Hab mal ne kleine IsPrime Erweiterung für BigInteger geschrieben.
Wie gut das Ding performancemäßig ist, kann ich allerdings nicht sagen. Auch nicht, ob die AsParallel Sache irgendwas bringt

Spoiler anzeigen

VB.NET-Quellcode

Imports System.Runtime.CompilerServices
Imports System.Numerics
Imports System.Threading.Tasks
Module Extensionmethods
''' <summary>
''' This function returns the largest BigInteger that multiplied with itself
''' is smaller or equal than the BigInteger to test
''' </summary>
''' <param name="num">The number of which the Sqrt should be calculated</param>
''' <returns>The Squareroot of num</returns>
''' <remarks></remarks>
<Extension()>
Public Function Sqrt(ByVal num As BigInteger) As BigInteger
If num < 0 Then Throw New System.ArgumentException("Must be 0 or greater", "num")
If num = 0 Then
Return BigInteger.Zero
ElseIf num < 4 Then
Return BigInteger.One
ElseIf num < 9 Then
Return New BigInteger(2)
End If
Dim j_min, j_max, j_tmp, r As BigInteger
j_min = BigInteger.One
j_max = num >> 1
While BigInteger.Add(j_min, BigInteger.One) < j_max
j_tmp = BigInteger.Add(j_min, j_max) >> 1
r = BigInteger.Multiply(j_tmp, j_tmp)
If r = num Then
j_min = j_tmp
Exit While
ElseIf r > num Then
j_max = j_tmp
Else
j_min = j_tmp
End If
End While
Return j_min
End Function
''' <summary>
''' This is just for storing some precalculated primes to increase performance
''' </summary>
''' <param name="b"></param>
''' <returns></returns>
''' <remarks></remarks>
<Extension()> Public Function PrecalculatedPrimes(ByVal b As BigInteger) As HashSet(Of BigInteger)
Static h As New HashSet(Of BigInteger) From {
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, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013,
1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069,
1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223,
1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291,
1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373,
1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451,
1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511,
1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583,
1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657,
1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733,
1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811,
1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889,
1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987,
1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053,
2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129,
2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213,
2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287,
2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357,
2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423,
2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531,
2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617,
2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687,
2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741,
2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819,
2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903,
2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999,
3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079,
3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181,
3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257,
3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331,
3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413,
3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511,
3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571,
3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643,
3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727,
3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821,
3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907,
3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989,
4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057,
4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139,
4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231,
4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297,
4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409,
4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493,
4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583,
4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657,
4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751,
4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831,
4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937,
4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003,
5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087,
5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179,
5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279,
5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387,
5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443,
5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521,
5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639,
5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693,
5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791,
5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857,
5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939,
5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053,
6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133,
6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221,
6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301,
6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367,
6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473,
6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571,
6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673,
6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761,
6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833,
6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917,
6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997,
7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103,
7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207,
7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297,
7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411,
7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499,
7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561,
7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643,
7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723,
7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829,
7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919,
7927}
Return h
End Function
<Extension()> Public Function IsPrime(ByVal num As System.Numerics.BigInteger) As Boolean
If num < 1 Then Throw New System.ArgumentException("Must be greater than 0", "num")
If num = 1 Then
Return False
ElseIf num = 2 OrElse num = 3 Then
Return True
End If
Static pcp As HashSet(Of BigInteger) = PrecalculatedPrimes(BigInteger.Zero)
' Is it one of our precalced primes?
If pcp.Contains(num) Then Return True
' Can it be divided by any of our precalced primes?
Dim sq As BigInteger = Sqrt(num)
Dim num_half As BigInteger = num >> 1
Dim r = (From p As BigInteger In pcp Where p <= sq AndAlso BigInteger.Remainder(num, p) = 0 Select p Take 1).AsParallel
If r.Count > 0 Then Return False
Debug.Print("hot candidate: " & num.ToString)
' Check for any number ABOVE the largest prime in our precalced primes
Dim i As BigInteger = PrecalculatedPrimes(BigInteger.Zero).Max
Dim l As New List(Of BigInteger)
While i <= sq
While l.Count < 10000
l.Add(i)
i += 2
If i > sq Then Exit While
End While
r = (From p In l Where BigInteger.Remainder(num, p) = 0 Select p Take 1).AsParallel
If r.Count > 0 Then Return False
l.Clear()
End While
Return True
End Function
End Module

petaod · 31. Mai 2011, 16:09

@picoflop: :thumbsup:

picoflop · 31. Mai 2011, 17:17

So, habs noch mal ein kleines bißchen optimiert (6k+1 bzw +5) und dann mal getestet:

VB.NET-Quellcode

Dim i As Numerics.BigInteger = UInt64.MaxValue
i += 1
Dim count As Integer = 0
Dim stp As New Stopwatch
stp.Start()
Do
count += 1
If i.IsPrime Then
Exit Do
End If
i += 1
Loop
stp.Stop()
TextBox1.Text = "Found " & i.ToString & " in " & count & " numbers in " & stp.Elapsed.ToString
MessageBox.Show("Found " & i.ToString & " in " & count & " numbers in " & stp.Elapsed.ToString)

Ergebnis:
Found 18446744073709551629 in 14 numbers in 00:07:50.0400636 (also knapp 8 Minuten)

Das ganze auf meinem nicht gerade schnellen Pentium Dual Core E6300 (2.8GHz). Gestartet aus der IDE als Release/x86

Jetzt müsste ich nur noch wissen ... ist 18446744073709551629 denn nun wirklich prim?

Und die anderen 13 Zahlen davor nicht? Die Online Tools die ich gefunden habe, helfen nicht, da sie nur bis max 15/16 Stellen prüfen, aber meine hat ja nun 20 Stellen.

Triple-Axe · 31. Mai 2011, 17:46

krass dein code

prim = prim wenn : nur durch 1 oder sich selber teilbar ...
wenn eine zahl ein gerades ende hat und nicht die komplette zahl nicht 2 ist : kein prim

mal eben von hand testen :

Quellcode

18446744073709551629 / 2 = 9223372036854775814,5 > könnte prim sein da , zahl
18446744073709551629 / 3 = 6148914691236517209,6666666666667 > könnte prim sein da , zahl
18446744073709551629 / 4 = 4611686018427387907,25 > könnte prim sein da , zahl
18446744073709551629 / 5 = 3689348814741910325,8 > könnte prim sein da , zahl
18446744073709551629 / 6 = 3074457345618258604,8333333333333 > könnte prim sein da , zahl
18446744073709551629 / 7 = 2635249153387078804,1428571428571 > könnte prim sein da , zahl
18446744073709551629 / 8 = 2305843009213693953,625 > könnte prim sein da , zahl
18446744073709551629 / 9 = 2049638230412172403,2222222222222 > könnte prim sein da , zahl
18446744073709551629/1=18446744073709551629 > is klar *G
18446744073709551629/18446744073709551629=1

ich behaupte : ist prim

hier ein onlineprimtester der es kann :

jjam.de/Java/Applets/Primzahlen/Miller_Rabin.html

jvbsl · 31. Mai 2011, 17:55

du musst aber mehr zahlen durchprobieren um das behaupten zu können...
Alles was du bei deinen Rechnungen umsonst gemacht hast, ist durch die jeweiligen Vielfachen zu teilen(also 4,3,8,9, da bei denen das Ergebnis klar war, aber was ist mit 11, 13, 17 und all den anderen schönen Primzahlen die noch reinpassen könnten?!)

Triple-Axe · 31. Mai 2011, 18:07

jvbsl schrieb:

du musst aber mehr zahlen durchprobieren um das behaupten zu können...
Alles was du bei deinen Rechnungen umsonst gemacht hast, ist durch die jeweiligen Vielfachen zu teilen(also 4,3,8,9, da bei denen das Ergebnis klar war, aber was ist mit 11, 13, 17 und all den anderen schönen Primzahlen die noch reinpassen könnten?!)

stimmt :pinch:

also eher mit de.wikipedia.org/wiki/Miller-Rabin-Test testen danke dir für den tip ich sollte mal pause machen

funktion um auf primzahl zu testen (zahlengröße 10000stellen und mehr)

funktion um auf primzahl zu testen (zahlengröße 10000stellen und mehr)

VB.NET-Quellcode

VB.NET-Quellcode

VB.NET-Quellcode

VB.NET-Quellcode

VB.NET-Quellcode

VB.NET-Quellcode

Quellcode

jvbsl schrieb:

Tags

Ähnliche Themen

4 Benutzer haben hier geschrieben