fork download
  1. ; strassen's factoring algorithm
  2.  
  3. (define (iroot k n)
  4. (let ((k-1 (- k 1)))
  5. (let loop ((u n) (s (+ n 1)))
  6. (if (<= s u) s
  7. (loop (quotient (+ (* k-1 u) (quotient n (expt u k-1))) k) u)))))
  8.  
  9. (define (strassen n)
  10. (call-with-current-continuation
  11. (lambda (return)
  12. (let ((c (iroot 4 n)))
  13. (do ((i 0 (+ i 1))) ((= i c) #f)
  14. (let* ((jmin (+ 1 (* i c))) (jmax (+ jmin c -1)))
  15. (do ((j jmin (+ j 1)) (f 1 (modulo (* f j) n)))
  16. ((< jmax j) (let ((g (gcd f n)))
  17. (when (< 1 g) (return g)))))))))))
  18.  
  19. (display (strassen 13290059)) (newline)
  20. (display (strassen 11111111111111111)) (newline)
  21. (display (strassen 2071723)) (newline)
Success #stdin #stdout 12.66s 43152KB
stdin
Standard input is empty
stdout
3119
2071723
#f