Вычислить следующие 3 простых числа с учетом int в Haskell

#haskell #time-complexity #prime-factoring

#haskell #временная сложность #разложение на простые множители

Вопрос:

Я пытаюсь написать функцию в Haskell, которая позволяет мне вычислять следующие 3 простых числа, учитывая значение N и сохранять три простых числа в отсортированном списке.

Задача состоит в том, чтобы сделать это без импорта какого-либо внешнего модуля.

Поведение функции:

* nextPrimes 75 = [79,83,89]

* nextPrimes 64 = [67,71,73]

он должен вычислить следующие 3 простых числа из N с 10-значными числами менее чем за 2 минуты.

nextPrimes :: Int -> [Int] nextPrimes n

1. Какой алгоритм вы хотите использовать для этого?

2. Я бы подошел к этому в Haskell, сначала сгенерировав бесконечный список простых чисел. Затем выполните поиск по этому списку, пока не дойдете до соответствующего места, и возьмите следующие три простых числа из списка.

Ответ №1:

извините… но я не смог удержаться…

 nextPrimes :: Int -> [Int]
nextPrimes n = let sq    = fromIntegral . ceiling . sqrt $ fromIntegral n
                   pri k = (k,and [ k`mod`x/=0 | x <- [2..sq]])
               in  take 3 . map fst . filter snd $ map pri [n..]

Это работает почти мгновенно, даже когда нам приходится считать до sqrt n:

 λ> nextPrimes 295084709089
[295084709159,295084709209,295084709273]

1. это потрясающе, большое спасибо, ценю это @oo_miguel

2. @DavidePollcino: Рад помочь. Итак, вы можете принять и проголосовать за этот ответ прямо сейчас 🙂

3. Спасибо за отзыв! Голоса, отданные теми, у кого репутация менее 15, записываются, но не изменяют публично отображаемую оценку публикации.

4. О, я не знал об этом.