Prime number checker unbelievably slow

I have this piece of code which checks whether a given number is prime:

If x Mod 2 = 0 Then
    Return False
End I开发者_如何转开发f
For i = 3 To x / 2 + 1 Step 2
    If x Mod i = 0 Then
        Return False
    End If
Next
Return True

I only use it for numbers 1E7 <= x <= 2E7. However, it is extremely slow - I can hardly check 300 numbers a second, so checking all x's would take more than 23 days...

Could someone give some improvements tips or say what I might be doing redundantly this way?

---

That is general algorithm for checking prime number. If you want to check prime number in bulk use algorithm http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

---

Look up the term "Sieve of Eratosthenes". It's a two thousand years old algorithm which is way better than yours. It's often taught in school.

---

You should definitely change your algorithm! You can try Sieve of Eratosthenes or a more advanced Fermat primality test. Beware that your code will be more complicated, as you would need to implement modular arithmetics. Look here for the list of some even more mathematically advanced methods.

---

You can also look for AKS primality test.
This is a good algorithm for checking primality.

---

Since x/2 + 1 is a constant through out the looping operation, keep it in a separate variable before the For loop. Thus, saving a division & addition operation every time you loop. Though this might slightly increase the performance.

---

Use the Sieve of Eratosthenes to create a Set that contains all the prime numbers up to the largest number you need to check. It will take a while to set up the Set, but then checking if a number exists in it will be very fast.

---

Split range in some chunks, and do checks in two or more threads, if you have multicore cpu. Or use Parallel.For.

---

To check if the number is prime you have only check if it can't be divided by primes less then it.

Please check following snippet:

 Sub Main()

        Dim primes As New List(Of Integer)
        primes.Add(1)

        For x As Integer = 1 To 1000
            If IsPrime(x, primes) Then
                primes.Add(x)
                Console.WriteLine(x)
            End If
        Next

    End Sub

    Private Function IsPrime(x As Integer, primes As IEnumerable(Of Integer)) As Boolean
        For Each prime In primes
            If prime <> 1 AndAlso prime <> x Then
                If x Mod prime = 0 Then
                    Return False
                End If
            End If
        Next
        Return True
    End Function

---

it slow because you use the x/2. I modified your code a little bit. (I don't know about syntax of VB, Maybe you have to change my syntax.)

If x < 2 Then
    Return False
IF x == 2 Then
    Return True
If x Mod 2 = 0 Then
    Return False
End If
For i = 3 To (i*i)<=x Step 2
    If x Mod i = 0 Then
        Return False
    End If
Next
Return True