# Short And Speedy Prime Factorization Programs For Casio Fx-9860gii Sd

3 replies to this topic

### #1 Jenab6

Jenab6

Newbie

• Members
• 14 posts
• Gender:Male
• Location:Hillsboro, West Virginia, USA
• Interests:Astronomy, math, physics, nationalist politics.

• Calculators:
CASIO fx-115ES, fx-9860g, fx-9860g ii SD
SHARP el-506a, el-509d, el-546g
Texas Instruments TI-89T
Base 8 DG-1000

Posted 11 December 2010 - 06:37 PM

Here is the code for my prime factors calculation program for the Casio fx-9860gii SD. It can factorize the integer 44355599 into the prime numbers 6659 and 6661 in 38.2 seconds. I will use this example as a benchmark.

"Prime factorize"
?→N
{N}→List 1
N→M
0→I
Lbl 1
If M<2 or Int M≠M
Then Goto 9
IfEnd
While MOD(M,2)=0
I+1→I
2→List 1[I]
MÃ·2→M
WhileEnd
1→K
Lbl 2
If M=1 Or K>M
Then Goto 9
IfEnd
K+2→K
If M=N And K>√N
Then Goto 9
IfEnd
While MOD(M,K)=0
I+1→I
K→List 1[I]
MÃ·K→M
WhileEnd
Goto 2
Lbl 9
List 1

There is some inefficiency in the program because after it finishes finding the divisors of 2 (if there are any) to the input number, it thereafter checks to see whether all of the odd-integers might be a divisor, whether the odd-integer is a prime or not. However, it seems to me that filtering out the composite odd-integers will require tests that might consume as much CPU time as just going ahead with the check.

This code will not work on the original fx-9860g calculator until you replace two lines.

While MOD(M,2)=0
is replaced by
While MÃ·2−Int(MÃ·2)=0

While MOD(M,K)=0
is replaced by
While MÃ·K−Int(MÃ·K)=0

However, when this is done, the Casio fx-9860g performs the same task in only 25.8 seconds, which is only 67.5% of the time required by its successor model, the fx-9860gii.

If anybody can create a speedier SHORT prime factorization code for the fx-9860gii SD, I'd like to see it in format like above shown.

Edited by Jenab6, 11 December 2010 - 07:03 PM.

### #2 Jenab6

Jenab6

Newbie

• Members
• 14 posts
• Gender:Male
• Location:Hillsboro, West Virginia, USA
• Interests:Astronomy, math, physics, nationalist politics.

• Calculators:
CASIO fx-115ES, fx-9860g, fx-9860g ii SD
SHARP el-506a, el-509d, el-546g
Texas Instruments TI-89T
Base 8 DG-1000

Posted 11 December 2010 - 10:00 PM

In the line that reads

If M=1 Or K>M

The last part isn't necessary, so change it to

If M=1

I made that change, and the program still works, with a gain of about 8% in speed. At the point where K=M, M is divided by K and assigned to M, leaving M=1, so K should never be greater than M. I think that I put the extra stop loop condition there while anticipating division round-off error which does not seem to be occurring.

### #3 Guest_bee_*

Guest_bee_*
• Guests

Posted 05 February 2011 - 12:06 PM

In the line that reads

If M=1 Or K>M

The last part isn't necessary, so change it to

If M=1

I made that change, and the program still works, with a gain of about 8% in speed. At the point where K=M, M is divided by K and assigned to M, leaving M=1, so K should never be greater than M. I think that I put the extra stop loop condition there while anticipating division round-off error which does not seem to be occurring.

hello
I have a casio graph 35 + and this is not working for me. Do I have to change something?

### #4 Guest_Anton_*

Guest_Anton_*
• Guests

Posted 01 May 2011 - 09:01 AM

Hello! I've made a factorization program that only takes one third of the time it takes for yours. It uses the fact that all primes except 2 and 3 can be expressed as 6kÂ±1. But note that I'm not used to Casio basic, so I'm sure I've missed a lot of optimization.

"FAKTOR"
{0}→List 1
1→I
?→N
While Frac (NÃ·2)=0
NÃ·2→N
2→List 1[I]
I+1→I
WhileEnd
While Frac (NÃ·3)=0
NÃ·3→N
3→List 1[I]
I+1→I
WhileEnd
5→F
While F≤√N
While Frac (NÃ·F)=0
NÃ·F→N
F→List 1[I]
I+1→I
WhileEnd
F+2→F
While Frac (NÃ·F)=0
NÃ·F→N
F→List 1[I]
I+1→I
WhileEnd
F+4→F
WhileEnd
N≠1=>N→List 1[I]
List 1

I sincerely hope that someone will write a more efficient factorization program than this, cause 12 seconds for an eight digit long number is slow.

#### 0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users