Dr² Sat (satangel) wrote,
Dr² Sat
satangel

  • Mood:
  • Music:

Приподнял голову над работой

Вчера полез смотреть определение простого числа, как будто бы я школу не с медалью закончил и никуда в жизть не поступал :)
Но ошибся поисковиком и попал на статью индийских ученых, опубликованную в 2002 году.
Там дается весьма эффективный алгоритм определения "простоты" числа, для математиков будет интересно.
С наброском алгоритма решения типовой задачи. Так вот обратите внимание на строчку 6 алгоритма. Про прохождении каждой итерации требуется нахождение максимального простого сомножителя, эээээ... Получается эдакое осовремененное решето Эратосфена, разве нет?

Статья: PRIMES is in P (Manindra Agrawal, Neeraj Kayal and Nitin Saxena)
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 

  • 0 comments