# Thread: Prime number support

1. ## Prime number support

While watching male lizards fight over females and slightly salted/cheesed biscuits during my vacation I've been pondering prime numbers.
Programming BigInt_IsPrime, _NextPrime and _PreviousPrime is not difficult. It is difficult to keep those functions fast for really big numbers.
As it turns out, I think the speed is acceptable.

I did some test just now, in (interpreted) thinBasic using the module as is, and checking if 100000000003 is prime (it is) takes 1.2 seconds (first attempt was 6.8 seconds) and finding the next prime number from that point (100000000019) also takes 1.2 seconds (first attempt was 6.9 seconds). This is of course in thinBasic, not as a module. Speed should increase significantly.

Working with prime numbers below 2^32 will be quite fast and up to 2^64 (my two examples mentioned above) I think the speed will still be acceptable. Above 2^64 (where the prime factors cross the magic 32-bit line) things will be slow. But that is of course up to the user.

So far I'm thinking of implementing BigInt_IfPrime, BigInt_NextPrime, BigInt_PrevPrime and BigInt_FactPrime. The last one will return an array with the prime factors of the given Big Integer. If anybody has suggestions for more functions dealing with primes, let me know in this thread.  Reply With Quote

2. Prime number support has been added. See the release in the sticky topic.  Reply With Quote

3. Hi Johannes
how to adapt this example about prime numbers to give a meaningfull results. i got only the first one to work, the other it displayed unwanted chars, only BigInt_IsPrime are working for me

```Uses "console"
Module "BigInt"
String someprime=BigInt_FromInteger(53)
Dim prime As Long
prime = BigInt_IsPrime(someprime)
PrintL prime
Dim a As String
a = BigInt_FromInteger(89)
PrintL BigInt_NextPrime(a)
Dim s As String
s="9"
Dim pf(2) As String
BigInt_FactPrime(s,pf)
PrintL pf(1)
PrintL pf(2)
s = BigInt_FromString("9")
BigInt_FactPrime(s,pf)
PrintL pf(1)
PrintL pf(2)
WaitKey
```  Reply With Quote

4. Zak,

Here is the changed script. Your main problem was that it is not possible to directly print Big Integers. You always need to use BigInt_ToString. Only conversion from string to Big Integer is automatic, not the other way around.
```Uses "Console"
Module "BigInt"

' Define a prime.
String someprime=BigInt_FromInteger(53)
' Find out if it really is a prime.
Dim prime As Boolean
prime = BigInt_IsPrime(someprime)
If prime Then
PrintL "Prime"
Else
PrintL "Not prime"
EndIf

' Directly print a larger prime.
Dim a As String
a = BigInt_FromInteger(89)
PrintL BigInt_ToString(BigInt_NextPrime(a))
' Variable a is still 89, not 97.
PrintL BigInt_ToString(a)

' Determine prime factors for a number.
Dim s As String
Dim i,n As Integer
s="9"
Dim pf(2) As String ' The '2' is not necessary. Dim pf() is enough.
BigInt_FactPrime(s,pf)
' Determine how many prime factors were returned.
n = UBound(pf)
' Print all prime factors using BigInt_ToString.
For i=1 to n
PrintL BigInt_ToString(pf(i))
Next i

' The next code works the same as the previous example
' because BigInt_FromString is automatic there.
s = BigInt_FromString("9")
BigInt_FactPrime(s,pf)
n = UBound(pf)
For i=1 to n
PrintL BigInt_ToString(pf(i))
Next i

WaitKey
```
I'll try to make proper example functions as soon as possible but that takes a lot of time and I still have to do all the bit stream stuff.

The most important thing to remember is that you cannot print a Big Integer directly. You must always use BigInt_ToString.  Reply With Quote

5. prime numbers functions is a valuable addition to thinbasic, i have tried to factor this number 123456789123456789 , and the results :
3*3×7×11×13×19×3607×3803×52579 so we can feel more freedom. thank you  Reply With Quote

6. Hi Johannes.

(I admit, this is sort of a dirty trick.)

Dan ****************************************

Programmer's Challenge

Code and perform the numerical calculation to determine with 100% certainty if the following integer is prime.

201487636602438195784363

****************************************  Reply With Quote

7. Well, of course I used google to see if this was a particular type of prime, and it is.

The number 201487636602438195784363 is the 12th Waggstaff prime W79. (Why not the 13th Wagstaff Prime W101? I love 13. )

Quoth Wikipedia:
Currently, the fastest algorithm for proving the primality of Wagstaff numbers is ECPP.
And this is what Wikipedia has to say about elliptic curve primality testing.

This would take me a year to program, assuming I am that good. So doing a BigInt_IfPrime and waiting the week (or two) would be faster.

Either way, I don't think so Dan.   Reply With Quote

8. never cease to be amazed at the unexpected turns while surfing the net,
just now while searching for the prime number that Dan posted above
found out about sexy primes http://en.wikipedia.org/wiki/Sexy_prime  Reply With Quote

9. Just for fun.

When someone gets some extra time.

Factor the following composite integer. 21130819027319923178509622632727980622577522491335986162202750512019525136688895741633235387039306968582318693021114825649130164135868576427684517893  Reply With Quote

10. That's a 111-digit number. Let me guess, does it consist of two 56-digit primes? This is why at first I was reluctant to add the prime number support. I told myself this would happen. Although I am convinced of the usefulness of BigInt, the one obvious drawback is that certain operations will be so slow as to be unusable. Multiplication, division, powers and roots of extremely large numbers are very, very slow. But anything having to do with prime numbers larger than, say, 15 decimal digits is just unworkable.

Maybe I'll put the factoring of that 111-digit number in my will.   Reply With Quote

Page 1 of 4 123 ... Last #### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•