(33s) Fermat Factorization

[Gerald H]

Fermat's factorization method is particularly good for finding large factors of a number, & very poor at finding small factors.

For example, for 608,391 (=3^4*7*29*37) the programme finds 777 almost instantaneously.

Consequently the method is most efficient in dealing with the "difficult" case of a composite number having two large prime factors.

The number 8616460799 is factorized in 49.6 s.

Code:

1.    LBL F
2.    STO A
3.    SQRT
4.    IP
5.    STO R
6.    SGN
7.    RCL+ R
8.    RCL+ R
9.    STO X
10.    SGN
11.    STO Y
12.    RCL+ Y
13.    x<> R
14.    SQ
15.    RCL-A
1.    LBL E
2.    x=0?
3.    GTO G
4.    RCL+ X
5.    x<> R
6.    STO+ X
7.    x<> R 
1.    LBLD
2.    RCL- Y
3.    x<> R
4.    STO+ Y
5.    x<> R
6.    x>0?
7.    GTO D
8.    GTO E
1.    LBL G
2.    RCL+ X
3.    RCL- Y
4.    RCL/ R
5.    RTN

F: LN = 45        D: LN = 24
E: LN = 21        G: LN = 15