HP 41C: 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 & 783 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 695 s.

1. LBL “FERM”
2. STO 00
3. SQRT
4. INT
5. RCL X
6. RCL Y
7. +
8. 1
9. STO T
10. +
11. STO Z
12. RDN
13. X^2
14. RCL 00
15. –
16. LBL 00
17. X=0?
18. GTO 01
19. RCL Y
20. +
21. 2
22. ST+ Z
23. RDN
24. LBL 02
25. RCL Z
26. –
27. 2
28. ST+ T
29. RDN
30. X>0?
31. GTO 02
32. GTO 00
33. LBL 01
34. RDN
35. X<>Y
36. –
37. 2
38. /
39. RCL 00
40. RCL Y
41. /
42. END