проект эйлера № 7 в схеме - PullRequest
Новая
       4

проект эйлера № 7 в схеме

4 голосов
/ 22 июня 2011

Вот вопрос:

Перечисляя первые шесть простых чисел: 2, 3, 5, 7, 11 и 13, мы можем видеть, что шестое простое число равно 13.

Что такое 10001-е простое число?

Вот мое решение: 

#lang racket

(define (search-limit num)
  (+ (floor (sqrt num)) 1))

(define (search-list num)
  (stream->list (in-range 2 (search-limit num))))

(define (divided? num x)
  (= (remainder num x) 0))

(define (list-of-dividers num)
  (filter (lambda (x)
            (divided? num x))         
       (search-list num)))

(define (prime? num)
  (= (length (list-of-dividers num)) 0))

(define (problem_7 current_prime primes counter)
  (cond
    [(< primes 10001)
     (cond
       [(prime? counter) (problem_7 counter (+ primes 1) (+ counter 1))]
       [else (problem_7 current_prime primes (+ counter 1))])]
    [else current_prime]))

(problem_7 0 0 0)

Это работает, но работает медленно.Я уверен, что есть лучшее решение.
Можете ли вы дать мне более схемное решение?

Ответы [ 2 ]

2 голосов
/ 22 июня 2011

Я сделал это следующим образом, который занимает менее 1 секунды на моем компьютере (ваша версия заняла около 12,5 секунд): 

#lang racket

(define (divides? n div)
  (= (remainder n div) 0))

(define (prime? n)
  (prime-helper n 2))

(define (prime-helper n start)
  (cond ((> start (sqrt n)) #t)
        ((divides? n start) #f)
        (else (prime-helper n (+ 1 start)))))

(define (prob7_helper n count)
  (cond ((= 10001 count) (- n 1))
        ((prime? n) (prob7_helper (+ 1 n) (+ 1 count)))
        (else (prob7_helper (+ 1 n) count))))

(define (prob7) (prob7_helper 2 0))

(prob7)

Конечно, есть более быстрые реализации (prime? n), но это делаеттрюк для меня.

1 голос
/ 22 июня 2011

Составные числа всегда имеют меньшее простое число в качестве делителя;простые числа никогда не имеют меньшего простого числа в качестве делителя.Поскольку вы генерируете простые числа в последовательности, вы можете использовать этот факт, выполнив тест на простоту, просто попробуйте разделить кандидата на список меньших простых чисел.(Кстати, это разновидность метода сита Эратосфена.)

...