prime nos.......

Hi,

This is an age-old question. How do u figure out whether a number is prime or not. I've never quite managed this. What if I have to display all prime nos. till a limit(say 1000/2000....not fixed)???

Thanks a lot,
Rammy.

I seem to recall the sieve of erastothenes(spelling??) was a way to get primes.
A good link seems to be
http://www.informatik.uni-frankfurt....ols/Sieve.html

thanks kleve....will check it out.......

Go Here:

http://www.planetsourcecode.com

and enter Prime Numbers in the Search Box.

Hey ! I played with this, here's some code,

It's pretty quick, it displays the number of and value of every prime up to a given number.

it did about 100000 per second, I was quite proud of it

open a project with a module and the following controls (sorry about the names, it's kinda n old project)

list1 (Listbox)
text1 (TextBox)
cmdFactor (button)
cmdPrint (button)

label1 (label)
label2 (label)
label6 (label)

put 100000 in the text box
press cmdfactor to calc
press cmdprint to copy to listbox

There are redundant functions becaue I found a pattern in primes which can speed up calculation by about 8-9 times and I didn't want to delete the old function.

Tell me how you go

Code:

---


' Module Code

Public primes() As Long
Public NoOfPrimes As Long

' Form code

Public Limit As Long

Private Sub cmdFactor_Click()

    Dim start As Single
    Dim low_total As Integer
    Dim NoLoop As Long
    Dim no_need As Boolean
   
    Limit = CLng(Text1.Text)
    If Limit < 2 Or Limit > 100000000 Then
        MsgBox ("Please type number from 2 to 100,000,000")
        Exit Sub
    End If
   
    If Limit < 1001 Then
        low_total = Limit
        no_need = True
    Else
        no_need = False
        low_total = 1000
    End If

    List1.Clear
    ReDim primes(Limit / 2 + 100)
   
    primes(1) = 2
    NoOfPrimes = 1
   
    start = Timer
   
    For NoLoop = 3 To low_total
   
        FindPrimes (NoLoop)
        If NoLoop Mod 1000 = 0 Then
            Label1.Caption = NoLoop & " Checked!"
            DoEvents
        End If
       
    Next
   
    If no_need = False Then
        For NoLoop = 1001 To Limit
            FindPrimes2 (NoLoop)
            If NoLoop Mod 1000 = 0 Then
                Label1.Caption = NoLoop & " Checked!"
                DoEvents
            End If
        Next
    End If
   
    Label2.Caption = Timer - start & " Seconds"
    MsgBox ("Done! " & NoOfPrimes & " Primes Found")

End Sub

Public Sub FindPrimes(candidate As Long)

    Dim search As Long
    Dim IsPrime As Boolean
   
    IsPrime = True
   
    For search = 1 To NoOfPrimes
        If candidate Mod primes(search) = 0 Then
            IsPrime = False
            search = NoOfPrimes + 1
        End If
    Next
   
    If IsPrime = True Then
        NoOfPrimes = NoOfPrimes + 1
        primes(NoOfPrimes) = candidate
    End If

End Sub

Private Sub cmdPercent_Click()
   
    Dim Half As Long
    Dim HalfCount As Long
    Dim List As String
    Dim List2 As String
   
    List = ""
    List2 = ""
    text2.Text = ""
   
    For x = 1 To NoOfPrimes
       
        Half = primes(x) / 2
       
        For y = 1 To NoOfPrimes
            If Half > primes(y) Then
                HalfCount = y
            Else
                y = NoOfPrimes + 1
            End If
        Next
       
        List = List & (x & vbTab & primes(x) & vbTab & (HalfCount / x * 100)) & vbTab & (x / primes(x) * 100) & vbCrLf
        If x Mod 100 = o Then
            List2 = List2 + List
            List = ""
            DoEvents
        End If
    Next
   
    text2.Text = List2
   
End Sub

Private Sub cmdPrint_Click()

    time1 = Timer
   

    List1.AddItem ("Count" & vbTab & "Prime")
    For x = 1 To NoOfPrimes
        List1.AddItem (x & vbTab & primes(x))
    Next
   
    time2 = Timer
   
    Label6.Caption = time2 - time1
   

End Sub

Public Sub FindPrimes2(candidate As Long)

    Dim search As Long
    Dim IsPrime As Boolean
   
    IsPrime = True
   
    For search = 1 To NoOfPrimes \ 9
        If candidate Mod primes(search) = 0 Then
            IsPrime = False
            search = NoOfPrimes + 1
        End If
    Next
   
    If IsPrime = True Then
        NoOfPrimes = NoOfPrimes + 1
        primes(NoOfPrimes) = candidate
    End If
   
End Sub

---

Just a thought.

Seeing as we know that a prime number can not be even, why not start the loop at an odd number (Paul did this), then use "Step 2" on the for loop. This way you won't ever check an even number. ;)

You know that there are prizes of $50,000+ for calculating primes of 1,000,000 digits!

My program slows from about 6.5 digits (500,000 primes)

I'd be stressed thinking about how to hold a figure 1,000,000 digits long!, probably a class with a byte array and functions to operate on the figure. so a long would sit in Bytes(0 to 3) etc...

That sort of stuff really fascinates me, wish I had the opportunity to go to Uni!

I seem to recall there being a Seti@Home like distributed client for prime calculation. The URL escapes me but I think I ran it for a bit at some point :)

I started Seti@home this month, I'd heard of it but never could be bothered, I've got 250hrs now!

try to remember, Primes are a more likely success than aliens in the short term!

Getting a little off topic but... :

I've been running seti for a while now :) The command line one runs a little faster, and if you use setiwatch & setilog, you can get nice detailed stats :) 7.5K hours and counting :)

BLATANT AD: Join my (rather small) VB Programmers team :
:D http://setiathome.ssl.berkeley.edu/c..._form&id=13999 :D

setti blowz, distributed.net's where it's at!

MOO

Thanks Paul, ur code worked fine...didn't need the second part, though (FindPrimes2).

Iain, ur suggestion was helpful as well.....it did reduce the time by a little bit.

Thanks a lot guys,
Rammy.

The code doesn't work without the findprimes2 function!

If you look the difference is the "For search = 1 To NoOfPrimes \ 9" line and that is what speeds things up.

The first 1000 primes are called with the find primes function but after that the findprimes2 function is called bacuse that's where the pattern starts.

If you want to do a speed test, copy the findprimes function to the findprimes2 function so they are the same then run a million primes, the difference is very big speed wise.

but I suppose if you only want to check a few thousand it doesn't really matter, just remember both are being called there.

Cheers