CODEWITHSUNDEEP
vb.netalgorithmprimes
pimvdb
pimvdb

Reputation: 154838

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 If
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?

Upvotes: 3

Views: 2029

Answers (9)

Toomtarm Kung
Toomtarm Kung

Reputation: 604

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

Upvotes: 0

Unlike
Unlike

Reputation: 153

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

Upvotes: 3

Oleg Rudckivsky
Oleg Rudckivsky

Reputation: 930

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

Upvotes: 0

gor
gor

Reputation: 11658

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

Upvotes: 0

Guffa
Guffa

Reputation: 700352

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.

Upvotes: 1

Mahesh
Mahesh

Reputation: 34625

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.

Upvotes: 1

Vlad
Vlad

Reputation: 35594

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.

Upvotes: 3

jmg
jmg

Reputation: 7414

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.

Upvotes: 4

Vivek Goel
Vivek Goel

Reputation: 24150

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

Upvotes: 6

Related Questions