Prime Numbers

[Code Doc]

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?

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.

[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.

[Code Doc]

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.

[storm5510]

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

Logophobic?

Where can I find this?

[Code Doc]

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.

[storm5510]

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

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.

[Code Doc]

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.

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