Wednesday, August 24, 2005

Is This Number Prime? : Three ( Terminus )

i have pretty much decided that this approach is not a very good one,
but i thought that i'd add two more little tid-bits before signing off on it...
---
One:
A better example of how the technique works.
Take a number 2081,
which i happen to know ( a-priori ) is prime...
and do a square root on it = 45.62
and create a list of primes up to 45.
{ 2 3 5 7 11 13 17 19 23 29 31 37 41 43 }
Then the most annoying aspect of this technique become obvious...
if you multiple all these together,
they are WAY over the original number,
so that if you convert the original number to that Base,
it's just the original number...!!!
So to get it to 'Work'-- You have to multiple the prime numbers together,
a few at a time, so that the 'last digit's' will be functional for our purposes...
2 * 3 * 5 * 7 = 210
Base 210 applied to 2081 is [9] [191]
191 is prime for 2, 3, 5 or 7
So far, so good.
But then it gets very tedious...!!!
You can't take any more than 2 primes at a time...!!!
11 * 13 = 143 = [14] [79]
17 * 19 = 323 = [6] [143]
23 * 29 = 667 = [3] [80]
80 is clearly NOT Prime, but it IS Prime for 23 or 29...???!!!
31 * 37 = 1147 = [1] [934]
41 * 43 = 1763 = [1] [318]
In each case; The resulting 'last digit' is prime for the numbers that contributed to the base for which 2081 was converted...
Meaning that 2081 is itself prime.
The program that does this takes about 5 times longer to tell me this than my brute force factorizing program...!!!
---
Two:
Then i somehow discovered a shorter version,
After realizing that a Base Convertion to find the Last Digit,
Is the long way around from a Simple MOD function...!!!
Using this approach, i created another program that is about 3 times FASTER than my brute force Factorizer... for large numbers...!!!
It is:

'C.P?'
Input is 1: Some Mysterious Integer
--
(rightarrow) (leftarrow)x
--
(leftarrow)x (squareroot) (zero) RND
(list of first 500 primes)
DUP DUP 4 ROLL x.L? ( subroutine in Is This Number Prime? : One )
NOT :: HEAD IFT POS 1 SWAP SUB
1
--
(leftarrow)x SWAP MOD SIGN NOT
--
DOLIST
(sigma)LIST SIGN
"Composite" "Prime" IFTE
(leftarrow)x SWAP -TAG
--
--
This works 100% of the time.
---

No comments: