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

---

Quote:

---

Originally Posted by TriLogic

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.

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.

---

I just got up from a nap and looked at this again and it makes perfect sense:

2 = 2
3 = 3
5 = 5
7 = 2
11 = 1 + 1 = 2
13 = 1 + 3 = 4
17 = 1 + 7 = 8
19 = 1 + 9 = 10 = 1 + 0 = 1
23 = 2 + 3 = 5
29 = 2 + 9 = 11 = 1 + 1 = 2

Those above are a small handful of little primes. It's a continual adding of digits until you have only one digit:

102 breaks up into 1 + 0 + 2. Add that and you get 3.

Amazing and simple. Implementation into code may be tough. I'll try it with VB6 first.

:)

Quote:

---

Originally Posted by Pradeep1210

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

---

What I'm getting at is just removing the even numbers from the start hence, only finding the odd numbers. This is because 2 can divide into any even number.

Once I started coding, it was actually really simple, and is it ever fast!

I need to test it more then I'll post it here.
.
.
Edit: There seems to be a problem. I'm getting a lot of non-prime numbers. I need to do more studying.

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.

---

This would be okay if the products of primes could be removed.

Quote:

---

Originally Posted by storm5510

This would be okay if the products of primes could be removed.

---

There are MANY WAYS to remove products of primes from this sequence. see PM

Quote:

---

Originally Posted by TriLogic

There are MANY WAYS to remove products of primes from this sequence.

---

If you could elaborate further, I would be grateful.

Quote:

---

Originally Posted by Nightwalker83

What I'm getting at is just removing the even numbers from the start hence, only finding the odd numbers. This is because 2 can divide into any even number.

---

That's exactly what it does. Since 2 is the smallest number, it eliminates all multiples of 2 (i.e. all even numbers) in the first loop. Then continues with 3 then 5 then 7 and so on.

The only difference between the two algorithms that make a performance difference is that while in SieveOfEratosthenes a number can come for elimination more than once, in EulersSieve any number can come for elimination only once.

Euler's Sieve is fine except for one thing. It relies on a list of primes previously found. I cannot do that. I have no limitation of numbers to sieve out. There could end up being billions(s). An array cannot hold all that, and the time involved in processing the contents, if it could hold it, would be really protracted.

I also have to periodically stop the program. Once done, any list would be gone. Using a list is simply not practical.

Quote:

---

Originally Posted by Pradeep1210

That's exactly what it does. Since 2 is the smallest number, it eliminates all multiples of 2 (i.e. all even numbers) in the first loop. Then continues with 3 then 5 then 7 and so on.

The only difference between the two algorithms that make a performance difference is that while in SieveOfEratosthenes a number can come for elimination more than once, in EulersSieve any number can come for elimination only once.

---

Ah ok cool!

Storm, I modified my code to run a little faster by ignoring even numbers. The prime numbers are now being written to a random access file as long integers. It will stop when the [2^31 - 1] limit is reached. I am predicting a final file size of about 1.6 Gb and am tracking the execution time. So far, it has been running 36 hours, and I am now generating big primes at the rate of about 20,000 per minute. Total file size is 160,000 Kb, so we are perhaps at the 10% point.

As expected, the program is slowing down as the numbers get larger. When it first took off, the primes were banging out at 500,000 per minute. Regardless of the lethargy at the top end, it's fun to occasionally watch Explorer update the file size as the primes are found and stored. I have made no concerted effort to shut down other programs, but most of the time I only run three or four in multi-tasking mode.

Now, what should I do with my 430 million or so long integer primes when it's all finished? :ehh:

@ Code Doc:

Well, I'm not going to be able to touch that on speed. I had to restart mine over again yesterday. That's what I get for experimenting with the code. I corrupted my data files. I have recovered back to 194 million primes in 2,164 data files.

I use registry keys in the program so I can stop it and restart again where it left off. I have it update these at 60 second intervals, or when I stop the program.

As the numbers have gotten larger, the per-file iteration time has increased. It is at 1.12 minutes per file with primes above 4 billion in value. When this time passes 5 minutes, I'll stop the process and wait for something new to come along to speed it back up again. Not sure what that will be yet. I started messing with this in 2005 on a P4. I gave it up when per-files time passed 5 minutes also.

What I mean by "per-file" is the amount of time it takes to create a 1 megabyte data file. I could have gone much larger with the data files, but I wanted Notepad to be comfortable with them and not crash.

Notepad? I would never allow that to constrain the processing. You can always write simple utility programs to extract the primes for subfiles that you can then tweak to display in Notepad, list boxes, grids, or whatever.

So, all my long integers are packed into one file that in essence represents a huge lookup table. The file is now approaching 180,000 Kb as I write. That's 45 million primes gathered to date.

I considered rewriting some of the code so that checking for previous primes could be done within the collection file to skip them and possibly improve speed. We used to do this years ago by reading in 1 Mb chunks into huge memory arrays as they became available. However, I think that read and skip routine could actually slow down the code inside the main loop. I may experiment with that after the file is completely built.

I suppose one possible use for this master file is that you can then check extremely fast if any number less that 2^31 is a prime using a search through the file. We can experiment with optimal search routines. Other than that, I am not sure what to do with the primes. Any other ideas?

Quote:

---

Originally Posted by Code Doc

Notepad? I would never allow that to constrain the processing...

I considered rewriting some of the code so that checking for previous primes could be done within the collection file to skip them and possibly improve speed...

I suppose one possible use for this master file is that you can then check extremely fast if any number less that 2^31 is a prime using a search through the file...

---

If someone that is very low on the computer literacy scale were to get a hold of these, well, you know. Besides, I don't see it as a constraint.

I still don't feel trying to use any type of list is practical if one has no limit of what they're trying to discover.

Speaking of limit, why 2^32?

2^32 is (about) the maximum size of an integer using 32 bit machines. Past that, the computer will either have to use floating point, causing you to lose low-order bits [i.e. 999999999999999999999 becomes 999999999999000000000], or you'll have to use more complicated representations, likely chaining together some integers.

What's the maximum size your function needs to handle?

This is why VB6 had a limitation on some features, like Mod, for example. It dates back to 1998, and things were not nearly as advanced as now.

The "Double" data type has been around for a long as I can remember. At the same time, I've seen large numbers lose some of their "weight" at the lower end, as in the example above.

Storm, I am only using long integers to store primes less then 2^31. After that, I will move on to stage II and use an 8-byte currency data type to hold larger ones. That will retain 15-digit accuracy to the left of the decimal and prime numbers up to 9,223,372,203,685,477. Even when stored packed, the collection of these enormous primes may exceed the capacity of my 160 Gb back up hard drive.

My long integer prime number file has now reached 250 Mb and contains about 63 million primes. The largest is just under 300,000,000. I'm about at the 15% mark in collecting them all for stage I in the processing. The collection rate had now dropped to 14,000 per minute or 20 million per day.

I project that just before the last long integer prime is found, the collection rate will have dropped to about 1200 per minute. That's the price of progress.

Now, what did you say we should do with all of them? :rolleyes:

Quote:

---

Originally Posted by Code Doc

Now, what did you say we should do with all of them? :rolleyes:

---

Was you not telling me of someone who wanted all primes up to 10^10?

;)

Edit: I'm past 55 hours total run time. 286 million primes found. Current max value is above 6 billion.

Storm said, "I'm past 55 hours total run time. 286 million primes found. Current max value is above 6 billion."
--------------
Terrific! Your program's collection rate now exceeds mine, assuming that you have found all the prime numbers. I have collected and stored only 70 million of them and I imagine the largest one is still much less than a billion in magnitude.

However, I'm only using one file to store them all. You said you are using several thousand files? :afrog: How do you intend to track all of them? Lose a few and you are toast. :rolleyes:

Quote:

---

Originally Posted by Code Doc

Storm said, "I'm past 55 hours total run time. 286 million primes found. Current max value is above 6 billion."
--------------
Terrific! Your program's collection rate now exceeds mine, assuming that you have found all the prime numbers. I have collected and stored only 70 million of them and I imagine the largest one is still much less than a billion in magnitude.

However, I'm only using one file to store them all. You said you are using several thousand files? :afrog: How do you intend to track all of them? Lose a few and you are toast. :rolleyes:

---

76 hours at 7.4 billion magnitude.

I'm using WinRAR to archive them in groups of 100. There are 36 archives so far. I need to catch it up again. There is an "index" file that is updated which gives the starting value of each data file. Below is an excerpt:

Quote:

---

P_003886.Txt Start = 7464216839
P_003887.Txt Start = 7466202691
P_003888.Txt Start = 7468184309
P_003889.Txt Start = 7470172309
P_003890.Txt Start = 7472164769

---

I keep duplicates of the archives on an external hard drive. I won't lose anything. ;)

My algorithm is very simple, testing each value for divisibility from 3 to N - 2 stepping in multiples of two; odd values only, excluding five.

Is N the size of the number being tested or its square root? You only have to check numbers for divisibility that are smaller than the square root of the number being considered. :ehh: