09-05-2022, 08:46 AM
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.
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