Smallest primes

Most Lisp implementations include a primitive called runtime that returns an integer that specifies the amount of time the system has been running (measured, for example, in microseconds). The following timed-prime-test procedure, when called with an integer n , prints n and checks to see if n is prime. If it's prime, the procedure prints three asterisks followed by the amount of time used in performing the test.

(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (runtime)))
(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (runtime) start-time))))
(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))

Using this procedure, write a procedure search-for-primes that checks the primality of consecutive odd integers in a specified range. Use your procedure to find the three smallest primes larger than 1000; larger than 10,000; larger than 100,000; larger than 1,000,000. Note the time needed to test each prime. Since the testing algorithm has order of growth of Θ(√n), you should expect that testing for primes around 10,000 should take about √10 times as long as testing for primes around 1000. Do your timing data bear this out? How well do the data for 100,000 and 1,000,000 support the √n prediction? Is your result compatible with the notion that programs on your machine run in time proportional to the number of steps required for the computation?


    # Александр
    3 months ago

    В тестах ошибки:

    1. Не определена функция runtime.
    2. В определении start-prime-test у if отсутствует ветка else. Возможно вместо if должно быть when.
    # Anton Burenkov Replied to Александр #
    3 months ago
    В тестах ошибки: 1. Не определена функция runtime. 2. В определении start-prime-test у if отсутствует ветка else. Возможно вместо if должно быть when.

    В тестах используется библиотека sicp - (require sicp) в котором определена функция runtime и допустим if без else. Но в данный момент имеются проблемы с её подключением

    # Anton Burenkov Replied to Anton Burenkov #
    2 months ago
    В тестах используется библиотека sicp - (require sicp) в котором определена функция runtime и допустим if без else. Но в данный момент имеются проблемы с её подключением

    На данный момент исключили библиотеку sicp из проверки данного упражнения, переопределили runtime, и вместо if стали использовать when

Authentication required

You must log in to post a comment.

Login