Иван Андреевич (diente_de_lion) wrote,
Иван Андреевич
diente_de_lion

Гениально!

Попалось мне это на википедии - не смог пройти мимо. Разложение числа на множители (конкретно на два множителя) при помощи регулярных выражений:
#!/usr/bin/perl -l

(1 x $_) !~ /^(11+)\1+$/ && print while ++ $_
Собственно такая вот незамысловатая прога печатает список простых чисел!

Как же оно работает? Как оказалось, очень просто. Числа последовательно перебираются, каждое представляется в виде строки из единиц соответствующей длины (3 в виде 111, 4 в виде 1111 и т.д.), а затем регекспом (и в этом вся соль!) эта строка представляется в виде более короткой подстроки (но не менее 2 символов), повторенной целое число раз. Если такое представление возможно - число составное. Иначе - простое :) Такое вот изящное решение. Еще хочу ))
Tags: перл
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 25 comments