1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
Sub atkin(ByVal l As Integer)
Dim primes(l) As Boolean, x2 As Integer = 0, y2 As Integer = 0, i As Integer = -1
For x As Integer = 1 To Math.Sqrt((l - 1) / 2)
i += 2
x2 += i
Dim j As Integer = -1
For y As Integer = 1 To Math.Sqrt(l - 1)
j += 2
y2 += j
Dim n As Integer = (x2 << 2) + y2
'Wenn n = 4x²+y² > l, sind weitere Vergleiche unnötig
If n Mod 2 = 1 AndAlso n <= l Then 'Gerade Zahlen werden übersprungen
If n Mod 12 = 1 OrElse n Mod 12 = 5 Then primes(n) = Not primes(n) '4x²+y²
n -= x2
If n Mod 12 = 7 Then primes(n) = Not primes(n) '3x²+y²
If x > y Then
n -= y2 << 1
If n Mod 12 = 11 Then primes(n) = Not primes(n) '3x²-y²
End If
Else
n -= x2
If n Mod 2 = 1 Then 'gerade Zahlen werden übersprungen
If n <= l Then
If n Mod 12 = 7 Then primes(n) = Not primes(n) '3x²+y²
If x > y Then
n -= y2 << 1
If n Mod 12 = 11 Then primes(n) = Not primes(n) '3x²-y²
End If
ElseIf x > y Then
n -= y2 << 1
If n <= l AndAlso n Mod 12 = 11 Then primes(n) = Not primes(n) '3x²-y²
End If
End If
End If
Next
y2 = 0
Next
Console.WriteLine(2 & vbNewLine & 3)
Dim l_sqrt As Integer = Math.Sqrt(l)
For x As Integer = 5 To l_sqrt Step 2
If primes(x) Then
Dim x22 As Integer = x * x
For y As Integer = x22 To l Step x22
primes(y) = False
Next
Console.WriteLine(x)
End If
Next
If l_sqrt Mod 2 = 0 Then l_sqrt += 1
For x As Integer = l_sqrt To l Step 2
If primes(x) Then Console.WriteLine(x)
Next
End Sub
|