Prime number generation - rapid algorithm required

[wossname]

I have just invented (It's probably been done by many different people in the last few thousand years, but I made it up myself this morning) an algorithm for generating a list of the first n prime numbers.

I start the list by supplying the first four terms, 3, 5, 7 and 11 (I'm ignoring 2) and when adding another to the list, I just grab the last term and add two. Then I try to divide the new number (x) by every prime in the list that comes before (and including) the square root of x.

It seems to be an efficient algorithm, apart from the fact that it only works if you have the entire list of primes up to the current term. So finding the 466428827442th term in the series would require serious RAM!

Does anyone know a faster way of generating say the first 1000 primes?

It's currently running on my Palm IIIx in PocketC. In terms of speed, it takes (-0.00002536n^3 + 0.03n^2 + 3.966n - 37.655) units of time to calculate n terms.

[DavidHooper]

yer this is good. it is roughly the same as dividing all values up to the sqrt x altho you store the past primes. so this is faster but requires more memory.

effectively an implementation of erasthotes <spelling!> sieve.

[Nucleus]

Sounds quite optimzed, other info here that probably won't add anything significant, but maybe:

http://www.vbforums.com/showthread.php?s=&threadid=94165&highlight=PrimeArray

[beachbum]

Am wondering what is larger, the number of known primes or the number of times that Nucleus has changed his avatar in the last few weeks :p

[Parke]

Nucleus:

Thanks for posting the old thread.

Parke

[Nucleus]

I know, even I don't know who I am anymore :(:D

[Guv]

You can speed your algorithm up slightly by starting at 7 and adding 6. Then check the sum and the number two less than the sum. This skips numbers divisible by three.

As a compromise between speed and memory requirements, you could use a list of the first 500-1000 primes. When you have tried every prime in the list as a divisor, then use odd divisors starting with the last prime in your list.

If the last prime is congruent to 7 mod 6, you can avoid the divisors which are divisible by three, by adding 6 to the last divisor and the sum and the sum less two.

[wossname]

Erathosthphanesdiplodicusironingboardnecrotelecomnicon, or something, yeah i know the guy you mean.

Well its not really like that because he does it from the other direction, he has a list of all normal numbers, 1,2,3,4,5,6,7,8.....10001,10002,10003, etc...

Then he starts at 2, and goes to every second number crossing it off his list, then he goes back to the start and crosses off every third number and so forth for all numbers ad infinitum.

All mine does is adds 2 to the current highest known prime, tests that against all previous primes, and increments it by two if it isn't a prime, and test again. Goes like s*** off a stick but its the memory problem that bugs me. :)

Interesting subject though, dont you think?

By the way, does anyone know any practical USES of prime numbers? I cant think of any at the moment apart from the well-documented RSA encryption methods.

[wossname]

Guv, ahhhh, no, can't do that...

If I start at 7 and add six, the program would think that the next prime after 7 is 13 ((7+6)) and in reality it is 11 ((7+2+2)) it ignores 9 because it is divisible by 3, so the second 2 is added and the program tests 11 and finds the prime.

Also, I am starting at 11 because int(sqr(11)) is 3, which is the first prime, my program includes the sqr root in the search.
If I started at 7 then the square root would be 2 ((2.64)) which is less then the first legal prime ((3 in this case because I am ignoring 2 as a matter of efficiency)). Therefore the program would hang.

I have struggled with this side of the algorithm for a few hours, and that i have now seems to be about as strong as I can get it.

My source code is written in PocketC, would anyone be interested in seeing it?

[DavidHooper]

http://161.58.186.97/showthread.php?threadid=100076


I perfected my use of prime numbers to find anagrams to now assign lower prime numbers to the most frequent letters of the english alphabet. It generates smaller word codes most of the time thus squeezing more out of a double data type.

[Guv]

I guess I did not describe the method properly.

If you start at 7 and add 6, you then check 13 and 11. Then you add 6 again and check 19 & 17. After adding 6, you check the sum and the number two less that the sum. This avoids checking numbers divisible by 3.

You can similarly avoid using divisors divisible by 3. Add 6 to the last divisor. Then use the sum and the sum less 2 as possible divisors.

Note that the above requires starting with primes congruent 7 mod one.

[Nucleus]

I see what you are saying Guv :)

Using the method described by Guv, I got approx 20% perfromance increase on my machine, nice work Guv :cool::


Private Declare Function GetTickCount Lib "kernel32" () As Long


Private Sub Command1_Click()
Dim a1, a2, start&, ms&

start = GetTickCount
a1 = PrimeArray(5000)
ms = GetTickCount - start
Debug.Print "Guv optimized approach: " & ms

start = GetTickCount
a2 = PrimeArray2(5000)
ms = GetTickCount - start
Debug.Print ms

End Sub


Function PrimeArray(numberOfPrimes As Long) As Long()
Dim found As Long, n As Long, i As Long, j As Long, sr As Long

'// we know the size of the result in advance
ReDim result(1 To numberOfPrimes) As Long

'// "2" is the first prime number
result(1) = 2
result(2) = 3

found = 2
n = 1

Do While found < numberOfPrimes

n = n + 4 'We are going to add 4 then 2, 4 then 2, etc
'to skip checking for numbers divisable by three

For j = 0 To 1

n = n + j * 2 ' add 2 as required

sr = Sqr(n)

'// let's check if N is a prime number
'// skipping check for 2 and 3 as these are redundant
For i = 2 To found

If (n Mod result(i)) = 0 Then Exit For

If result(i) >= sr Then
'canot have factor > square root, so n must be prime
found = found + 1
result(found) = n
Exit For
End If

Next i

Next j

Loop
PrimeArray = result
End Function


Function PrimeArray2(numberOfPrimes As Long) As Long()
Dim found As Long, n As Long, i As Long, sr As Long

'// we know the size of the result in advance
ReDim result(1 To numberOfPrimes) As Long

'// "2" is the first prime number
result(1) = 2: found = 1
n = 1

Do While found < numberOfPrimes
'// all other prime numbers are odd, so we can skip even numbers
n = n + 2
sr = Sqr(n)

'// let's check if N is a prime number
For i = 1 To found

If (n Mod result(i)) = 0 Then Exit For

If result(i) >= sr Then
'canot have factor > square root, so n must be prime
found = found + 1
result(found) = n
Exit For
End If

Next

Loop
PrimeArray2 = result
End Function

[Nucleus]

got slightly more speed by skipping 5 as well:


Function PrimeArray(numberOfPrimes As Long) As Long()
Dim found As Long, n As Long, i As Long, j As Long, sr As Long

'// we know the size of the result in advance
ReDim result(1 To numberOfPrimes) As Long

'// "2" is the first prime number
result(1) = 2
result(2) = 3
result(3) = 5
result(4) = 7
result(5) = 11
result(6) = 13

found = 6
n = 15

Do
For j = 1 To 8

If j = 1 Then
n = n + 2
ElseIf j = 2 Then n = n + 2
ElseIf j = 3 Then n = n + 4
ElseIf j = 4 Then n = n + 6
ElseIf j = 5 Then n = n + 2
ElseIf j = 6 Then n = n + 6
ElseIf j = 7 Then n = n + 4
ElseIf j = 8 Then n = n + 2
End If

sr = Sqr(n)

'// let's check if N is a prime number
'// skipping check for 2 and 3 and 5 as these are redundant
For i = 4 To found

If (n Mod result(i)) = 0 Then Exit For

If result(i) >= sr Then
'canot have factor > square root, so n must be prime
found = found + 1
result(found) = n
If found = numberOfPrimes Then
PrimeArray = result
Exit Function
End If
Exit For
End If

Next i

Next j
n = n + 2

Loop
End Function

[macai]

Can somebody post a way to make sure a number is prime?

Public Function IsPrimeNumber(Number as Long) As Boolean
'Procedure
End Function


So,

MsgBox IsPrimeNumber(2)

would spew out "True" and

MsgBox IsPrimeNumber(4)

would spew "False".

Somebody write that funciton. PLEASE. :D

[macai]

Hay. I wrote a relatively relevant function. Well, you guys wrote
how to generate the prime numbers. Now, i wrote a function
which will the the same thing in reverse. What it will do is tell if a
number is a prime number or not. Cool, huh?Public Function IsDecimal(Number) As Boolean
Dim splitted() As String
splitted = Split(Number, ".")
If UBound(splitted) <> 0 Then
IsDecimal = True
End If
End Function

Public Function IsPrimeNumber(Number) As Boolean
For i = 2 To Number - 1
'MsgBox i & Chr(10) & i * Number & Chr(10) & IsDecimal(Number / i)
If IsDecimal(Number / i) = False Then
IsPrimeNumber = False
Exit Function
End If
Next i
IsPrimeNumber = True
End FunctionPeace out! :D

[da_silvy]

Why not just:


Function IsPrime(CheckNum As Integer) As Boolean
If CheckNum Mod 3 = 0 Or CheckNum Mod 4 = 0 Or CheckNum Mod 5 = 0 Or CheckNum Mod 7 = 0 Or CheckNum Mod 9 = 0 Then
IsPrime = False
Else
IsPrime = True
End If
End Function

Private Sub Form_Load()
MsgBox IsPrime(15)
End Sub

[Guv]

I wrote a program for my HP48GX hand calculator which uses a table of 169 primes from 2 to 1009, inclusive. The table speeds the process up a bit, which is necessary for a hand calculator, but but not make much difference to a PC. The program uses Mod Operator to check for divisibility by one of the primes in the list. When the list of primes is exhausted, use following two steps alternately.

add 4 to last divisor to get next possible divisor.

Add 2 to last divisor to get next two possible divisor.At each stage, check the possible divisor versus the square root of the number being investigated. When the potential divisor is greater than the square root, the program terminates.

Note that the list of primes must end in a prime which is congruent to zero mod 6. Id est: If you divide by 6 the remainder must be one. Otherwise alternately adding 2 & 4 will not work properly.

My program actually finds all prime factors. It starts by putting the input number into a list. It checks the top number in the list using the above algorithm. If it finds a prime factor, it replaces the top number in the list with the prime factor and the other factor. It then works on the top number in the list, et cetera, and terminates when it can find no more prime factors. The list containing all prime factors is then displayed.

The above should not be difficult to program using Visual Basic. I suppose you could use a List Box to hold the original number and replace it with all the prime factors. Using Long variables would allow checking numbers up to 2 147 483 647. I am not sure if Double variables could be used for numbers with about 14 decimal digits. It might not be too tuff to program the arithmetic required to work with 64-bit numbers held in two Long variables, restricting the divisors to Long variables.

[wossname]

da_silvy, because 289 (for example) is not a prime number (its 17*17) and it is not divisible by any of those numbers you put in your bit of code. So the if statement would set the return value to true when it really isn't.

ps, 9 isnt prime either. :)

[Nucleus]

Perhaps you could create an array of prime array where the maximum number in the prime array is less than the sqare root of the the number being tested. Then just check to see if the number is in the array or not.

[wossname]

Something just occurred to me: If you keep adding numbers to the 'skip list' then you will eventually be doing the same amount of work as the straightforward skip 2 method but in reverse. How strange, smells a bit like a paradox to me, I wonder what the optimal length of this skip list is. I strongly suspect that it should contain only 2.

Thatths my hypothethith on the thubject!

[Nucleus]

Function IsPrime(ByVal Number) As Boolean
' Optimised isPrime function

Dim check&, SR#, j&

If Number = 2 Or Number = 3 Or Number = 5 Or Number = 7 Or Number = 11 Or Number = 13 Then
' if 2,3,5,7,11,13 then must be a prime
IsPrime = True
Exit Function
End If

If Number Mod 2 = 0 Or Number Mod 3 = 0 Or Number Mod 5 = 0 Or Number Mod 7 = 0 _
Or Number Mod 11 = 0 Or Number Mod 13 = 0 Then
' if not 2,3,5,7,11,13, yet divisable by these nums then can't be prime
Exit Function
End If

SR = Sqr(Number)
check = 15

' Now instead of checking the mod of each integer less than a number to see if it is
' prime, we can skip checks for numbers divisable by 2,3 and 5 meaning the algorithm is
' mucho optimised. Also the alogorithm terminates when the checking integer increases
' passed the square root of number, which further optimises the algo.
Do
For j = 1 To 8

If j = 1 Then
check = check + 2
ElseIf j = 2 Then check = check + 2
ElseIf j = 3 Then check = check + 4
ElseIf j = 4 Then check = check + 6
ElseIf j = 5 Then check = check + 2
ElseIf j = 6 Then check = check + 6
ElseIf j = 7 Then check = check + 4
ElseIf j = 8 Then check = check + 2
End If


' If check > SR, as you can't have a factor greater than a number's
' square root, it must be prime.
If check > SR Then
IsPrime = True
Exit Function
End If

' This number has a factor, so can't be prime
If Number Mod check = 0 Then Exit Function

Next j
check = check + 2

Loop

End Function

[Guv]

Nucleus: Your algorithm is difficult to assess.

It seems correct to ignore the preliminary code, since it is critical to economize when working with a huge number which has only large prime factors. Hence, analysis of the Do Loop should tell the tale.

BTW: I never realized that VB had a Do Forever Loop. I always thought that a While or Until Condition was required.

My basic idea of add 4, then add two results in doing the Mod Operation & Square Root comparison twice for each triplet of odd numbers. Id est, it skips one third of the odd numbers (.333). It requires a Do-Until loop, but neither a For Loop nor any decision commands other than those absolutely required to determine primeness and avoid looping forever.

Your algorithm results in doing the Mod Operation & Square Root comparison 8 times for every group of 14 odd numbers. Id est, it skips 3 / 7 of the odd numbers (.429).

There seems to be a lot of decision making overhead, especially for j = 6, 7, or 8 and there is the For Loop overhead. I have a hunch that you might not save much time over a simpler program.

With a much longer program, you could implement the same algorithm without the For Loop and the If-ElseIf Statements. For speed, this might be the way to go. Trade memory space for speed by using a longer program.

[Nucleus]

Guv

I noticed that I got a performance increase from the prime array function you helped me write to skip 2 and 3. When I noticed that skipping 2 and 3 saved a lot of time, I played around with a few series until I worked out you could skip 5 as well, and got 10% performance increase by writing the more complex program to do so. I just reworked the algo to create this function to test for primeness (is that a word?). Although I haven't tested it for speed, I am pretty sure the same benefits would apply.

From memory I don't think you could write a program to skip 7. So apart from including a list of primes with the app, like you pointed out, I think this should be pretty fast.

[Nucleus]

Guv

what did you mean by:

"With a much longer program, you could implement the same algorithm without the For Loop and the If-ElseIf Statements"

[Guv]

Nucleus: I am too lazy to write it all out, but the idea is to put the following into the Do Loop.
Check = Check + 2
If Check > SR Then
IsPrime = True
Exit Function
End If

If Number Mod Check = 0 Then
IsPrime = False
Exit Function
End If

Check = Check + 2
If Check > SR Then
IsPrime = True
Exit Function
End If

If Number Mod Check = 0 Then
IsPrime = False
Exit Function
End If

Check = Check + 4
If Check > SR Then
IsPrime = True
Exit Function
End If

If Number Mod Check = 0 Then
IsPrime = False
Exit Function
End If

Check = Check + 6
If Check > SR Then
IsPrime = True
Exit Function
End If

If Number Mod Check = 0 Then
IsPrime = False
Exit Function
End If
. . . Using Cut & paste, it is not too tuff to create the 8 sets of statements necessary to create the above program.

I included some unnecessary IsPrime = False statements.

BTW: As a matter of style, I never rely on Compiler defaults. I would have an IsPrime = False Statement at the beginning of the Function, and not repeat it so many times.

[Nucleus]

I see now, yeah, that would speed it up even more.

[jemidiah]

There is another way. You could use a For loop to simply test the number instead of accessing and finding prime numbers before. There are a few special cases (positives and evens) but other than that, the main part should work. Also, this is pretty fast for me. I got up to 60,000,001 starting from zero using a variation of this in a couple hours.


Public Function isNumPrime(TestNumber As Double) As Boolean

'A few special cases
'Negatives and zero
If TestNumber =< 0 Then
isNumPrime = False
Exit Function
End If
'Just what it says
If TestNumber = 2 Then
isNumPrime = True
Exit Function
End If
'Evens
If Int(TestNumber / 2) = TestNumber / 2 Then
isNumPrime = False
Exit Function
End If

'For positive, non even numbers
For i = 3 To Int(Sqr(TestNumber)) + 1 Step 2 'Only check until the
'square root, skipping evens. Added 1 just in case.

'If division create a whole number, it isn't prime
If Int(TestNumber / i) = TestNumber / i Then
isNumPrime = False
Exit Function
End If

Next i

'If it gets through, it is prime
isNumPrime = True

End Function

[riis]

A few possible optimizations:

1) Use "blah mod x = 0" instead of "int(blah/x) = blah/x". I've just tested it, and for me it's about 2.6 times faster.
2) There's no need for TestNumber to be a double. Prime numbers are always integers and if you use long integer, there's no need for (implicit) conversion to long
3) Store Int(Sqr(TestNumber)) + 1 in a temporary variable (of type long, of course). This way this expression is evaluated every time in the for loop. Adding 1 is not necessary.
4) Don't test for TestNumber = 2. You know this is a prime number, but now this test is executed for all numbers. Find another way to include it in your list.

Good luck. I'm curious to know how much this will improve the performance :)

[jemidiah]

Thanks. I had been looking for a better way to determine if there was a remainder than the int method. With the new way, I can get the prime number to go up by about 100,000 (+/-) in 14.61 seconds at around 61,000,000. Not checking multiples of three after the number three would skip 1/6th of the loop. I have added a line right after it executes the loop again to see if it is a multiple of three, but that just made it slower. Is there any way to tell vb to skip multiples of numbers inside the for loop?

[Nucleus]

Originally posted by jemidiah
Thanks. I had been looking for a better way to determine if there was a remainder than the int method. With the new way, I can get the prime number to go up by about 10,000 (+/-) in 2.73 seconds at around 61,000,000. Not checking multiples of three after the number three would skip 1/6th of the loop. I have added a line right after it executes the loop again to see if it is a multiple of three, but that just made it slower. Is there any way to tell vb to skip multiples of numbers inside the for loop?

Just wondering how long does the algorithm I posted about 8 posts up fair?

[jim mcnamara]

For testing large numbers consider this discussion from
http://www.anujseth.com/crypto/prime.html

What this means is that the number of arithmetic operations to determine if a number is prime is greatly reduced over any brute force division method.


Home » The Data Encryption Page » Prime Numbers

Prime Numbers
Some characteristics of primes

Every integer n greater than 1 can be expressed as a product of primes (with perhaps only one factor)
There are arbitrarily large gaps in the series of primes
The number of primes is infinite. That is, there is no end to the sequence of primes
The factoring of any integer n > 1 into primes is unique apart from the order of the prime factors
If p is a prime then (p - 1)! = -1 mod p. (Wilson’s Theorem)
The RSA cryptographic algorithm uses a lot of prime numbers in generating its keys. These keys in turn will hold the strength of the encryption.

Public-key algorithms need prime numbers. Any reasonably sized network needs lots of them. Before discussing the mathematics of prime number generation, we will answer a few obvious questions.

If everyone needs a different prime number, won’t we run out? No. In fact, there are approximately 10151 primes 512-bits in length or less. For numbers near n, the probability that a random number is prime is approximately one in ln n. So the total number of primes less that n is n/(ln n). There are only 1077 atoms in the universe. If every atom in the universe needed a billion new primes every microsecond from the beginning of time until now, you would only need 10109 primes.
What if two people accidentally pick up the same prime number? It won’t happen. With over 10151 prime numbers to choose from, the odds of that happening is significantly low.
If someone creates a database of all primes, won’t he be able to use that database to break public-key algorithms? Yes, but he can’t do it. If you could store one gigabyte of information on a drive weighing one gram, then a list of just the 512-bit primes would weight so much that it would exceed the Chandrasekhar limit and collapse into a black hole &ldots; so you couldn’t retrieve the data anyway.
But if factoring numbers is so hard, how can generating prime numbers be easy? The trick is that the yes/no question, "Is n prime?" is a much easier question to answer than the more complicated question, "What are the factors of n?"

The wrong way to find primes is to generate random numbers and then try to factor them. The right way is to generate random numbers and test if they are prime. There are several probabilistic primality tests; tests that determine whether a number is prime with a given degree of confidence. Assuming this "degree of confidence" is large enough, these sorts of tests are good enough.

Various primality-testing algorithms include:

Solovay-Strassen Test
Lehmann Test
Rabin-Miller Test
Fermat’s Test
The algorithm everyone uses was developed by Michael Rabin, based in part on Gary Miller’s ideas. Actually, this is a simplified version of the algorithm recommended in the DSS proposal.


--------------------------------------------------------------------------------

Rabin-Miller Test
Choose a random number, p, to test. Calculate b, where b is the number of times 2 divides p-1. Then calculate m, such that p = 1 + 2b*m.

1. Choose a random number, a, such that a is less than p.
2. Set j = 0, and set z = am mod p.
3. If z = 1, or if z = p - 1, then p passes the test and may be prime.
4. If j > 0 and z = 1, then p is not prime.
5. Set j = j +1. If j < b and z <> z2 mod p go back to step 4. If z = p - 1, then p passes the test and may be prime.
6. If j = b and z <> p -1, then p is not prime.
The odds of a composite passing decreases faster with this test than with previous ones. Three-quarters of the possible values of a are guaranteed to be witnesses. This means that a composite number will slip through t tests no more than ¼t of the time, where t is the number of iterations. Actually, these numbers are very pessimistic. For most random numbers, something like 99.9 percent of the possible a values are witnesses.


--------------------------------------------------------------------------------

Fermat’s Test
If p is a prime, then Fermat’s test says 2p mod p = 2

This can be used as an additional level of testing, during the prime number generation phase.


--------------------------------------------------------------------------------

Practical Considerations
In real-world implementations, prime generation goes quickly.

Generate a random n-bit number, p.
Set the high-order and low-order bit to 1. (The high-order bit ensures that the prime is of the required length and the low-order bit ensures that it is odd.)
Check to make sure p is not divisible by any small primes: 3, 5, 7, 11 and so on. Many implementations test p for divisibility by all primes less than 256. The most efficient is to test for divisibility by all primes less than 2000.
Perform the Rabin-Miller test for some random a. If p passes, generate another random a and go through the test again. Choose a small value of a to make the calculations go quicker. Do five tests. (One might seem like enough, but do five!). If p fails one of the tests, generate another p and try again.
Another option is not to generate a random p each time, but to incrementally search through numbers starting at a random point until you find a prime.

Step (3) is optional, but it is a good idea. Testing a random odd p to make sure it is not divisible by 3, 5, and 7 eliminates 54 percent of the odd numbers before you get to step (4). Testing against all primes less than 100 eliminates 76 percent of the odd numbers; testing against all primes less than 256 eliminates 80 percent. In general, the fraction of odd candidates that is not a multiple of any prime less than n is 1.12/ln n. The larger the n you test up to, the more precomputation is required before you get to the Rabin-Miller test.

[Lior]

Originally posted by wossname
Erathosthphanesdiplodicusironingboardnecrotelecomnicon, or something, yeah i know the guy you mean.



You probably mean Eratosthenes, a Greek mathematician who invented a method for discovering primes, which is called: "Sieve of Eratosthenes".

[NotLKH]

Originally posted by jim mcnamara
Fermat’s Test
If p is a prime, then Fermat’s test says 2p mod p = 2

:confused:
it seems to me that
2p mod p = 0, for all p.
Originally posted by jim mcnamara
). There are only 1077 atoms in the universe

:confused:
and
Originally posted by jim mcnamara
If every atom in the universe needed a billion new primes every microsecond from the beginning of time until now, you would only need 10109 primes.

I'm lost.


:confused:

[sql_lall]

I have made a very fast program to find primes, but it is written in C++, and was wondering if it is still OK for me to post it.

Also, i think he meant something like 2^p-1 = 1(mod p )

[wossname]

Sure post away, most VB'ers will be able to translate C++ as long as it doesn't have stuff like op overloading and stuff like that.