Si bien la Criba de Eratóstenes es el metodo mas rapido ese codigo que colocastes no funciona
hice getPrimes(1000), se salta varios primos y hay compuestos en la lista como el 995, no hay ningun primo que termine en 5 y se salto el 751 que es un primo.
Así estaría bien aplicado y mas corto
Public Function Primes(ByVal N As Long) As Long()
If N < 3 Then
Return New Long() {}
End If
Dim _Tabla As New BitArray(N - 2), _
_Primes As New List(Of Long), _
_P As Byte() = New Byte() {2, 3, 5, 7}
Dim Y As Long = 2
For Each X As Byte In _P
Do While (X * Y) < N
_Tabla((X * Y) - 2) = True
Y += 1
Loop
Next
Y = 0
Do While Y < (_Tabla.Length - 1)
If Not _Tabla(Y) AndAlso _
Not (Math.Sqrt(Y + 2) = CLng(Math.Sqrt(Y + 2))) Then
_Primes.Add(Y + 2)
End If
Y += 1
Loop
Return _Primes.ToArray()
End Function