gistfile1.scm

(define (pick-random n)
  "Retorna um inteiro randômico entre 1 e n-1"
  (+ 1 (random (- n 1))))

;; quanto maior a tolerância, maior a certeza de que o número
;; é realmente um primo, e não um primo composto. Porém o tempo
;; do algoritmo é proporcional à tolerância, então 10 é um número
;; razoável
(define tolerancia 10)

;; Teorema de Fermat
(define (prime? n)
  ; realiza o loop no máximo n vezes, onde n é a tolerancia
  (let ((return #t))
    (do ((i 1 (+ i 1)))
        ((or (= i tolerancia) (eqv? return #f)))
      (let ((a (pick-random n)))
        (if (not (= (modulo (expt a (- n 1)) n) 1))
            (set! return #f))))
    return))

(define (mersenne m)
  (let ((lista-mersenne ())) 
    (do ((i 2 (+ i 1)))
      ((= (length lista-mersenne) m)) ; condicao de parada. se tamanho da lista for igual a m.
        (if (primo? (- (expt 2 i) 1)) ; verifica se eh primo (2^n - 1), se for, adiciona na lista
          (set! lista-mersenne (cons (- (expt 2 i) 1) lista-mersenne)))) 
   lista-mersenne))