Prime Numbers

Is there a simple algorithm which can determine if a number is prime?

I've looked at several and all are very time consuming to do very large numbers.

No; you can't get both fast and simple. Also, a professor of mine is referenced on one of those pages, that was unexpected :).

I didn't think so but I thought I would ask.

I found this interesting:

Code:

---

A) Start with all the natural numbers except '1' which is not a prime.
  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...
  ^
B) The leftmost number is prime. Multiply each number in the list by this prime and discard the products.
  2 3  5  7  9    11    13    15    17    19    21    23    25    27    29    31    33    35...
    ^
C) The number after the previous prime is also a prime. Multiply each number in the list starting from
  the latest prime by the latest prime and discard the products.
  2 3  5  7        11    13          17    19          23    25          29    31          35...
        ^
Repeat C) indefinitely. On each repetition a new prime is identified (marked ^) until all the primes in
the starting list have been found.

---

Discard the products?

2 x 2 = 4.... take the 4 out of the list. 2 x 3 = 6, now remove 6 from the list. 2 x 4 = 8, remove 8... repeat ad nauseum.

-tg

I'm curious, how large are the numbers you're using?

Quote:

---

Originally Posted by jemidiah

I'm curious, how large are the numbers you're using?

---

Up to 10^9 and perhaps beyond in the future. I have something I wrote and it seems to work.

Code:

---

' If result = 0 then number is composite.

half = Fix(Sqr(number))

For denom = 2 To half
    result = (number / denom) - Fix(number / denom)
    If result = 0 Then
        Exit For
    End If
Next denom

---

I give it a range which it steps through and outputs the results to a text file. I don't used "Mod" as it has a size limit. I think "Sqr" is okay being any number to the half power. i.e. number^0.5.

You can Step 2 to cut the computation time about in half (though you need to start at 3 and check 2 separately that way). 10^9 isn't actually very large. That fast algorithm I linked would probably be slower on such a "small" number. To be honest I was envisioning RSA-size primes of 1000+ digits.

I've been a participant in the GIMPS project since 2005. They're dealing with Mersenne prime numbers millions of digits in length. The largest do date has 12,837,064 digits, in the form of 2^42643801. It was discovered on April 12 of this year. Below is a link to their site.

http://www.mersenne.org/

Quote:

---

Originally Posted by storm5510

Is there a simple algorithm which can determine if a number is prime?

---

If you are attempting to discover new primes then I strongly suggest you narrow the field by just focusing on ODD Numbers with DIGITAL ROOTS of 1,4,7,2,5,8. These numbers will be either primes or products of primes > 3 multiplied by primes > 3.

All other numbers:

EVEN numbers with digital roots 1,4,7,2,5,8
ODD & EVEN numbers with digital roots 3,6,9

will be multiples of 2 or 3 or multiples of both 2 & 3.

Quote:

---

Originally Posted by TriLogic

If you are attempting to discover new primes then I strongly suggest you narrow the field by just focusing on ODD Numbers with DIGITAL ROOTS of 1,4,7,2,5,8. These numbers will be either primes or products of primes > 3 multiplied by primes > 3.

All other numbers:

EVEN numbers with digital roots 1,4,7,2,5,8
ODD & EVEN numbers with digital roots 3,6,9

will be multiples of 2 or 3 or multiples of both 2 & 3.

---

Can you elaborate on this just a little more? I am not sure I understand the phrase "digital root".

I am checking odd numbers ending with 1, 3, 7, and 9. I am using a loop division to check each number in steps of 2.

Quote:

---

Originally Posted by storm5510

Can you elaborate on this just a little more? I am not sure I understand the phrase "digital root".

I am checking odd numbers ending with 1, 3, 7, and 9. I am using a loop division to check each number in steps of 2.

---

The problem with checking numbers with terminating digits of 1,3,7 and 9 is that they will include multiples of 3 such as 9,(15),21, 27, 33, 39,...,just keep adding 6 to these numbers and the pattern repeats.(includes terminating digit 5) as 1,7,3,9,5,1,7,3,9,5,...,None of these numbers in this sequence towards infinity are prime.

Calculating Digital Roots is a method of summing individual digits of any number to a single digit number between 1 and 9.

http://en.wikipedia.org/wiki/Digital_root.

9 = 9
21 = 2 + 1 = 3
27 = 2 + 7 = 9
33 = 3 + 3 = 6
39 = 3 + 9 = 12 = 1 + 2 = 3

31 = 3 + 1 = 4
37 = 3 + 7 = 10 = 1
43 = 4 + 3 = 7



Any numbers with Digital Root of 3, 6 or 9 will not be a prime number. So calculating digital roots is useful method of 'rooting out' odd numbers which terminate with 1,3,7,9, that have digital roots of 1,4,7 and 2,5,8 but not 3,6 or 9.

ODD Numbers with digital roots 1,4,7 are found in sequence 1 + 6 = 7 + 6 = 13 + 6 = 19 + 6 = 25 + 6 = 31You can add 12 to terminating digit 9 to eliminate 5's

So 6n + 1 = digital root of 1, 4 or 7
And 6n - 1 = digital root of 2, 5, or 8.

The results of these calculations will give either Prime Number or a prime > 3 multiplied by a prime/primes > 3. This is significant because all other prime factors for all other numbers are based on 2^n and/or 3^n

Primes emerge within two streams: One emerging from the number 1 + multiples of 6 towards infinity. And the other stream emerging from the number 5 + multiples of 6 towards infinity.

The odd numbers to check are within:

1, 7, 13, 19, (25), 31,...stream containing digital roots 1, 4, or 7

or

5, 11, 17, 23, 29, (35), 41....,stream containing digital roots 2, 5 or 8

Sorry if this sounds too confusing to be of any use :sick:

How fast do u need it?
This is just a basic one and it takes less that half a second to list all primes upto 100,000

vb Code:

Dim primeNumbers As New List(Of Integer)
Dim isPrime As Boolean
primeNumbers.Add(2)
For i As Integer = 3 To 100000 Step 2
    isPrime = True
    For Each n As Integer In primeNumbers
        If i Mod n = 0 Then isPrime = False : Exit For
    Next
    If isPrime Then primeNumbers.Add(i)
Next

Quote:

---

Originally Posted by TriLogic

Sorry if this sounds too confusing to be of any use.

---

It is. I need to study it more.

Quote:

---

Originally Posted by Pradeep1210

This is just a basic one and it takes less that half a second to list all primes upto 100,000

---

And if one wanted to run this indefinitely? What I mean is, it would take a bit more.

I appreciate everyone replies. :) What I am using is below:

Code:

---

Function IsPrimeA(ByVal N As ULong) As Short

        Dim C As ULong

        IsPrimeA = 0

        Half = N ^ 0.5

        For C = 3 To Half Step 2
            If N Mod C = 0 Then Exit Function
        Next

        IsPrimeA = 1
        Return IsPrimeA

End Function

---

The digital root tests are conceptually nice, but they require numbers to be stored in base 10 to be efficient, and are basically just as powerful as dividing a couple of times is, likely over-complicating things (at least for a base 2 computer). The code you listed should work fine, up until the limit of the "mod" function. For obscenely large number different methods are needed, but I don't think you're in that range (in fact, if you were, you'd likely need to be using some form of string arithmetic anyway, and your problem could easily get intractable).

My "fast" link above is apparently the quickest*, provably correct algorithm for finding primes in existence. It's also a bit of a monster. The one you've done is the simplest, and will work quite well for small primes. It's very, very similar to the "simple" link, the Sieve.


*quickest for all numbers past some point; that point might be larger than the number of atoms in the universe, so you better be using *very* large numbers to bother.

I suspect I will hit a wall with Mod at 2^32 (4,294,967,296). If I do, I have a work-around I found in the local documentation:

Code:

---

a - (b * Fix(a / b))

---

Did you notice my usage of a "half-power"? I can only assume that square root is gone. All I know is that "Sqr" didn't have any meaning. I tried some variations without success.

Using ^0.5 one time when you're looping millions (or more) of times is no biggee. I dunno what they did with the function, I still use VB6.

This is interesting :D. I compared a few methods and this is what I have:

vb.net Code:

Private Const MAX As ULong = 10000000
Private Const OutputFormat As String = "{0}. {1} Prime numbers Found in {2} ms"
 
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
    Dim primeNumbers As New List(Of ULong)
    Dim sw As New Stopwatch
 
    Debug.Print("Normal Method:")
    For pass As Integer = 1 To 5
        sw.Reset()
        sw.Start()
        primeNumbers = NormalMethod()
        sw.Stop()
        Debug.Print(OutputFormat, pass, primeNumbers.Count, sw.ElapsedMilliseconds)
        Application.DoEvents()
    Next
 
    Debug.Print("Sieve Of Eratosthenes:")
    For pass As Integer = 1 To 5
        sw.Reset()
        sw.Start()
        primeNumbers = SieveOfEratosthenes()
        sw.Stop()
        Debug.Print(OutputFormat, pass, primeNumbers.Count, sw.ElapsedMilliseconds)
        Application.DoEvents()
    Next
 
    Debug.Print("Euler's Sieve:")
    For pass As Integer = 1 To 5
        sw.Reset()
        sw.Start()
        primeNumbers = EulersSieve()
        sw.Stop()
        Debug.Print(OutputFormat, pass, primeNumbers.Count, sw.ElapsedMilliseconds)
        Application.DoEvents()
    Next
End Sub
 
Private Function NormalMethod() As List(Of ULong)
    Dim primeNumbers As New List(Of ULong)
    Dim isPrime As Boolean
 
    For i As ULong = 3 To MAX Step 2
        isPrime = True
        For j As Long = 0 To primeNumbers.Count ^ 0.5 - 1
            If i Mod primeNumbers(j) = 0 Then isPrime = False : Exit For
        Next
        If isPrime Then primeNumbers.Add(i)
    Next
    primeNumbers.Insert(0, 2)
    Return primeNumbers
End Function
 
Private Function SieveOfEratosthenes() As List(Of ULong)
    Dim primeNumbers As New List(Of ULong)
    Dim numbers(MAX) As Integer '1 = prime, -1 = not prime
 
    For i As ULong = 2 To MAX
        If numbers(i) = 0 Then
            numbers(i) = 1
            primeNumbers.Add(i)
            For j As ULong = i To MAX Step i
                numbers(j) = -1
            Next
        End If
    Next
    Return primeNumbers
End Function
 
Private Function EulersSieve() As List(Of ULong)
    Dim primeNumbers As New List(Of ULong)
    Dim numbers(MAX) As Integer '1 = prime, -1 = not prime
 
    For i As ULong = 2 To MAX
        If numbers(i) = 0 Then
            numbers(i) = 1
            primeNumbers.Add(i)
            For j As ULong = i To MAX
                Dim pos As ULong = j * i
                If pos > MAX Then Exit For
                numbers(pos) = -1
            Next
        End If
    Next
    Return primeNumbers
End Function

Result:

Code:

---

Normal Method:
1. 664579 Prime numbers Found in 21563 ms
2. 664579 Prime numbers Found in 21550 ms
3. 664579 Prime numbers Found in 21547 ms
4. 664579 Prime numbers Found in 21540 ms
5. 664579 Prime numbers Found in 21561 ms
Sieve Of Eratosthenes:
1. 664579 Prime numbers Found in 952 ms
2. 664579 Prime numbers Found in 1190 ms
3. 664579 Prime numbers Found in 2410 ms
4. 664579 Prime numbers Found in 2540 ms
5. 664579 Prime numbers Found in 2468 ms
Euler's Sieve:
1. 664579 Prime numbers Found in 1639 ms
2. 664579 Prime numbers Found in 1627 ms
3. 664579 Prime numbers Found in 1633 ms
4. 664579 Prime numbers Found in 1630 ms
5. 664579 Prime numbers Found in 1668 ms

---

Yes, very interesting. Thank you. :)

I am not sure how I would implement this as it uses a list. My function receives one number at a time with no limit as to how large the number is.

The Mod function is past 2^32 now. No problems. So, I'll just stick with it and see how far it can go.

Below is another variation I came across:

Code:

---

i = Sqr(M)
        For j = 0 To i Step 60
            If M Mod (j + 11) = 0 Then Exit Function
            If M Mod (j + 13) = 0 Then Exit Function
            If M Mod (j + 17) = 0 Then Exit Function
            If M Mod (j + 19) = 0 Then Exit Function
            If M Mod (j + 23) = 0 Then Exit Function
            If M Mod (j + 29) = 0 Then Exit Function
            If M Mod (j + 31) = 0 Then Exit Function
            If M Mod (j + 37) = 0 Then Exit Function
            If M Mod (j + 41) = 0 Then Exit Function
            If M Mod (j + 43) = 0 Then Exit Function
            If M Mod (j + 47) = 0 Then Exit Function
            If M Mod (j + 53) = 0 Then Exit Function
            If M Mod (j + 59) = 0 Then Exit Function
            If M Mod (j + 61) = 0 Then Exit Function
            If M Mod (j + 67) = 0 Then Exit Function
            DoEvents
        Next j

---

ok.. so let's modify our functions to test whether the given number is prime number or not.

vb.net Code:

Private Const OutputFormat2 As String = "{0}. Result = {1}      Time Taken = {2} ms"
 
Private Sub Button2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button2.Click
    Dim IsPrime As Boolean
    Dim sw As New Stopwatch
 
    Dim number As ULong = ULong.Parse(TextBox1.Text)
 
    Debug.Print("Testing whether " & TextBox1.Text & " is Prime Number or not ...")
 
    Debug.Print("Normal Method:")
    For pass As Integer = 1 To 5
        sw.Reset()
        sw.Start()
        IsPrime = IsPrimeByNormalMethod(number)
        sw.Stop()
        Debug.Print(OutputFormat2, pass, IsPrime, sw.ElapsedMilliseconds)
        Application.DoEvents()
    Next
 
    Debug.Print("Sieve Of Eratosthenes:")
    For pass As Integer = 1 To 5
        sw.Reset()
        sw.Start()
        IsPrime = IsPrimeBySieveOfEratosthenes(number)
        sw.Stop()
        Debug.Print(OutputFormat2, pass, IsPrime, sw.ElapsedMilliseconds)
        Application.DoEvents()
    Next
 
    Debug.Print("Euler's Sieve:")
    For pass As Integer = 1 To 5
        sw.Reset()
        sw.Start()
        IsPrime = IsPrimeByEulersSieve(number)
        sw.Stop()
        Debug.Print(OutputFormat2, pass, IsPrime, sw.ElapsedMilliseconds)
        Application.DoEvents()
    Next
End Sub
 
Private Function IsPrimeByNormalMethod(ByVal number As ULong) As Boolean
    Dim primeNumbers As New List(Of ULong)
    Dim isPrime As Boolean
 
    For i As ULong = 3 To number Step 2
        isPrime = True
        For j As Long = 0 To primeNumbers.Count ^ 0.5 - 1
            If i Mod primeNumbers(j) = 0 Then isPrime = False : Exit For
        Next
        If isPrime Then primeNumbers.Add(i)
    Next
    primeNumbers.Insert(0, 2)
    Return primeNumbers.Contains(number)
End Function
 
Private Function IsPrimeBySieveOfEratosthenes(ByVal number As ULong) As Boolean
    Dim numbers(number) As Integer '1 = prime, -1 = not prime
 
    For i As ULong = 2 To number
        If numbers(i) = 0 Then
            numbers(i) = 1
            For j As ULong = i * 2 To number Step i
                numbers(j) = -1
            Next
            If numbers(number) <> 0 Then Exit For
        End If
    Next
    Return numbers(number) = 1
End Function
 
Private Function IsPrimeByEulersSieve(ByVal number As ULong) As Boolean
    Dim numbers(number) As Integer '1 = prime, -1 = not prime
 
    For i As ULong = 2 To number
        If numbers(i) = 0 Then
            numbers(i) = 1
            For j As ULong = i To number
                Dim pos As ULong = j * i
                If pos > number Then Exit For
                numbers(pos) = -1
            Next
            If numbers(number) <> 0 Then Exit For
        End If
    Next
    Return numbers(number) = 1
End Function

Testing against 16769023, this is what I get on my system:

Code:

---

Testing whether 16769023 is Prime Number or not ...
Normal Method:
1. Result = True      Time Taken = 45153 ms
2. Result = True      Time Taken = 46126 ms
3. Result = True      Time Taken = 46061 ms
4. Result = True      Time Taken = 46116 ms
5. Result = True      Time Taken = 45119 ms
Sieve Of Eratosthenes:
1. Result = True      Time Taken = 1801 ms
2. Result = True      Time Taken = 4053 ms
3. Result = True      Time Taken = 4183 ms
4. Result = True      Time Taken = 4225 ms
5. Result = True      Time Taken = 4184 ms
Euler's Sieve:
1. Result = True      Time Taken = 2718 ms
2. Result = True      Time Taken = 2863 ms
3. Result = True      Time Taken = 2781 ms
4. Result = True      Time Taken = 2774 ms
5. Result = True      Time Taken = 2797 ms

---

aah.. it seems like this test is flawed..
1. We don't need to loop thru and store the prime numbers in IsPrimeByNormalMethod() function, which would bring down the time taken.
2. I can't get past the INTEGER limit for number of items in array. So the IsPrimeBySieveOfEratosthenes() and IsPrimeByEulersSieve() don't really work for LONG datatypes.

Please ignore the above post.

There is something I don't get here:

Line 73 shows a dimension statement for an array. Why an array for only one number at a time?

Quote:

---

Originally Posted by storm5510

There is something I don't get here:

Line 73 shows a dimension statement for an array. Why an array for only one number at a time?

---

How else would we keep a track of which numbers we have crossed out as not primes? :)

Quote:

---

Originally Posted by storm5510

It is. I need to study it more.




And if one wanted to run this indefinitely? What I mean is, it would take a bit more.

I appreciate everyone replies. :) What I am using is below:

Code:

---

Function IsPrimeA(ByVal N As ULong) As Short

        Dim C As ULong

        IsPrimeA = 0

        Half = N ^ 0.5

        For C = 3 To Half Step 2
            If N Mod C = 0 Then Exit Function
        Next

        IsPrimeA = 1
        Return IsPrimeA

End Function

---

---

Interestingly this function categorizes 18446744073709551608 as a prime number.. though I don't exactly know why. Clearly this number is not prime as it ends in 8 and is thus divisible by 2.

okk... I get it now.
You missed testing it with 2

So it should be something like this:

vb.net Code:

Private Function IsPrimeA(ByVal number As ULong) As Boolean
    If number Mod 2 = 0 Then Return False
    For C As ULong = 3 To number ^ 0.5 Step 2
        If number Mod C = 0 Then Return False
    Next
    Return True
End Function

And the biggest prime number we would be able to test with it is 18446744073709551557.

Sieve of Eratosthenes

This might help

I feel silly that I didn't catch that divisible by 2 case (especially when I had mentioned it earlier, "...though you need to start at 3 and check 2 separately that way..."). Whoops.

Have a look at this class
http://www.codeproject.com/KB/cs/biginteger.aspx

This seems to have a capacity more than ULong and also has a method to determine whether a number is prime or not. Though I've not used it or tested its performance.

http://go.internet.com/?id=474X1146&...iginteger.aspx

Server Not Found
.
.

2^49836383

How does anyone represent something like this in a computer and work with it? This is 15,002,247 digits long.

Jemediah, Techgnome, et al. OP said he only needed primes up to 10^10 in size. Why not use Logophobic's prime number generator (or mine which is a bit slower) to first generate and store all of these primes in a file. Then search the appropriate file to see if a match exists.

If it does not, then that solves the problem. Seem reasonable? :ehh:

Quote:

---

Originally Posted by Code Doc

Jemediah, Techgnome, et al. OP said he only needed primes up to 10^10 in size...

---

I had to quote this just to make sure I was seeing it properly.

10^10 is 10,000,000,000. Wow!

I have everything up to 4,346,078,071. I have 2,299 files of 1 MB each. They are packed into RAR archives of 100 files each. Average archive size is 20 MB, so the pack very well. There is also an index.

I wonder. Could you store these as 4-byte long integers that could reach 2,147,483,648 in size? You pick up 1 byte for every prime larger than 9,999, 2 bytes for every prime larger than 99,999, etc. Not sure if that helps any, but the compression improves as the primes get bigger and there are more of them at the top than at the bottom. The first 200 million primes would thus require 800 Mb.

How large is the 200 millionth prime number? :ehh:

After you get above 2^31, you could then go to a file using 8-byte currency to store numbers up to 16-digit accuracy to the left.

I'm writing them as plain text using StreamWriter and WriteLine.

As the numbers get larger, the time to create one file grows. At present, it takes 90 seconds. I guess I should not complain. It could be a lot worse. I have an older variant I did with VB6. That one was slow.

I run this on a Core 2 Duo. Despite what I've read, it appears to use both cores when running.

=====

Edit: It seems to me there should be some way to do this with logarithms.

Quote:

---

Originally Posted by storm5510

I'm writing them as plain text using StreamWriter and WriteLine.

As the numbers get larger, the time to create one file grows. At present, it takes 90 seconds. I guess I should not complain. It could be a lot worse. I have an older variant I did with VB6. That one was slow.

I run this on a Core 2 Duo. Despite what I've read, it appears to use both cores when running.
=====
Edit: It seems to me there should be some way to do this with logarithms.

---

I think you may have forgotten to use Logophobic's code to generate the prime numbers. I have seen nothing faster than his program, and I have given up writing code that can beat it.

Second, consider my recommendation. Store all prime numbers on disk that are less than 2^31 as long integers. Then store the larger ones and all future ones on subsequent files as currency that requires 8 bytes per prime. Your program can continuously check the value of the prime and store the number in the appropriate files as needed. That's a small sacrifice.

Eventually, the mass storage capacity of your computer will be exceeded, but that may take hours to accomplish. Meanwhile, you can display the progress of your program using standard VB6 controls.

Quote:

---

Originally Posted by Code Doc

I think you may have forgotten to use Logophobic's code to generate the prime numbers.

---

Logophobic?

Where can I find this?

I don't believe logarithms would help store prime numbers more compactly. The compression ratio should be wonderful, though, if you store primes in a file--but then, you're sacrificing speed while you uncompress the file. How quickly do you need to test primality?

There are a wide number of fast probabilistic tests. A simple one is the Fermat Primality Test. The modular exponentiation can be done quickly; the number of exceptions (if you run the full test) is relatively small--there are only 32 in the numbers from 1 to 500,000.

Quote:

---

Originally Posted by techgnome

2 x 2 = 4.... take the 4 out of the list. 2 x 3 = 6, now remove 6 from the list. 2 x 4 = 8, remove 8... repeat ad nauseum.

-tg

---

Wouldn't an easier way be to remove any number that "2" can go into? :D

Quote:

---

Originally Posted by Nightwalker83

Wouldn't an easier way be to remove any number that "2" can go into? :D

---

SieveOfEratosthenes and EulersSieve in post #17 There is just a small difference between the two, but that has a considerable difference on performance.

Quote:

---

Originally Posted by storm5510

Logophobic?

Where can I find this?

---

Here's a good thread to study:
http://www.vbforums.com/showthread.p...t=Prime+Number

Note my suggestions. Also Merri shows a link to his code, which is usually spotless and certainly worth examining. Note that my code may be slower but does not require the memory array of primes that Logophobic's code does. That will be a problem when your list of stored primes becomes huge.

This looks good, but with on caveat. It uses a list.

Code:

---

Dim MyNumber As Long
  Dim Root As Long
  Dim Prime(19999) As Long
  Dim Count As Long
  Dim I As Long
 
  MyNumber = 2
  Prime(0) = 2
  Count = 1
  Do While Count < 20000
    MyNumber = MyNumber + 1
    Root = Int(Sqr(MyNumber))
    I = 0
    Do Until Prime(I) > Root
      If MyNumber Mod Prime(I) = 0 Then Exit Do
      I = I + 1
    Loop
    If Prime(I) > Root Then
      Prime(Count) = MyNumber
      Count = Count + 1
    End If
  Loop
 
  List1.Clear
  For I = 0 To 19999
    List1.AddItem CStr(Prime(I))
  Next I

---

I need to be able to run without using a list. Each value I find is sent to a data file. There is no ceiling on the number of values. I designed my program to be able to run for years, literally.

It's easy to send the prime to a data file once it is found, and I recommend a random access file. However, Logophobic's code is limited by the array size-- Prime(19999). So, 20,000 numbers is about it for a list box. You can likely bump that to several million and store them on disk, but I thought your objective was to get billions of them. So, the array of primes is out.

Take a look at my slower but simple code that does not require an array. It would be easy to add the prime to a random access file and store the first 2^31 primes as 4-byte long integers. Then when that limit is reached, close that file and open up another file and store the rest of the primes as an 8-byte currency variable. The code below is limited to the long integer.

Code:

---

Dim MyNumber As Long, NumFactors As Integer, PrimeCount as Long

Private Sub Form_Load()
MyNumber = 1
Do
    NumFactors = 0
    MyNumber = MyNumber + 1
    For I = 1 To Sqr(MyNumber)
        If MyNumber / I = MyNumber \ I Then
            NumFactors = NumFactors + 1
            If NumFactors > 1 Then Exit For ' Not a prime
        End If
    Next
    If NumFactors = 1 Then ' Prime Found
        PrimeCount = PrimeCount + 1
        ' Store prime on disk using code here

    End IF
Loop
End Sub

---