Наименьшие простые числа

Большая часть реализаций Лиспа содержат элементарную процедуру runtime , которая возвращает целое число, показывающее, как долго работала система (например, в миллисекундах). Следующая процедура timed-prime-test , будучи вызвана с целым числом n , печатает n и проверяет, простое ли оно. Если n простое, процедура печатает три звездочки и количество времени, затраченное на проверку.

(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))

Используя эту процедуру, напишите процедуру search-for-primes , которая проверяет на простоту все нечетные числа в заданном диапазоне. С помощью этой процедуры найдите наименьшие три простых числа после 1000; после 10 000; после 100 000; после 1 000 000. Посмотрите, сколько времени затрачивается на каждое простое число. Поскольку алгоритм проверки имеет порядок роста Θ(√n), Вам следовало бы ожидать, что проверка на простоту чисел, близких к 10 000, занимает в √10 раз больше времени, чем для чисел, близких к 1000. Подтверждают ли это Ваши замеры времени? Хорошо ли поддерживают предсказание √n данные для 100 000 и 1 000 000? Совместим ли Ваш результат с предположением, что программы на Вашей машине затрачивают на выполнение задач время, пропорциональное числу шагов?


    # Александр
    3 месяца назад

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

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

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

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

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

Необходима авторизация

Вы должны авторизоваться для создания комментария.

Вход