Comments 35
Подсветку кода бы еще, а так за статью спасибо, будет, что рассказать=)
Подскажите нормальный сайтик, на котором это можно будет сделать, что бы хабровский типограф не порезал половину — сделаю.
А то я пытался и получается какая-то фигня.
Пытался через tohtml.com/java/
А то я пытался и получается какая-то фигня.
Пытался через tohtml.com/java/
Так, с подсветкой разобрались.
Как решить вопрос с переключением контекстов в многозадачных операционных системах? Ведь при их переключении бОльшая часть кеша заполняется совсем другими данными.
Ну на самом деле криптография использует решето Аткина. И основной проблемой является все таки определение является ли это число простым. Эта проблема решена для чисел Мерсена и чисел Ферма, но тест простоты для других чисел обладает высокой сложностью.
Цель статьи обучающая, как простыми инструментами добиться приемлемых результатов. Эратосфен не претендует на первенство, но он прост и понятен, чаше всего в небольших задачах этого достаточно.
Алгоритм AKS, являющийся детерминированным и полиномиальным, написанный на Java:
для 100 бит отрабатывает за три секунды
для 150 бит — за 7 секунд
для 200 бит — за 23 секунды
для 250 бит — за 35,5 секунды
далее экстраполируйте сами :)
Core i7 920 2,6GHz
для 100 бит отрабатывает за три секунды
для 150 бит — за 7 секунд
для 200 бит — за 23 секунды
для 250 бит — за 35,5 секунды
далее экстраполируйте сами :)
Core i7 920 2,6GHz
Лучше реализовать на битовом массиве — минимальное потребление памяти.
Множество цифр числа Пи и множество простых чисел бесконечны. Ведутся работы по доказанию гипотезы о возможной конечности последовательности простых близнецов и чисел Софи Жермен.
Что касаемо числа Пи, то для абсолютного большинства практических задач такой точности не нужно. И я, честно говоря не вижу большого смысла в уточнении этого числа. Разве что как сомнительный источник случайной последовательности.
Простые же числа более интересны. Во первых, не все гипотезы связанные с ними доказаны, во вторых большие простые числа активно используются в гражданской криптографии (RSA, алгоритм Диффи-Хеллмана) и думаю применяются еще в дюжине достаточно узких направлений математики.
Простые же числа более интересны. Во первых, не все гипотезы связанные с ними доказаны, во вторых большие простые числа активно используются в гражданской криптографии (RSA, алгоритм Диффи-Хеллмана) и думаю применяются еще в дюжине достаточно узких направлений математики.
Эмм… Постарался на ваш.
Для большинства практических задач необходимые точности были получены еще несколько веков назад. Однако существуют и будут существовать направления, где нужны будут очень большие числа или точности.
Для большинства практических задач необходимые точности были получены еще несколько веков назад. Однако существуют и будут существовать направления, где нужны будут очень большие числа или точности.
В первом комменте я ответил что их бесконечно много. И как следствие найти максимальное такое число нельзя. Нельзя взять и сказать: «А знаете нам пожалуй этого числа хватит, давайте перестанем искать и назовем его максимальным».
Или я опять не понимаю вашего вопроса? Если так объясните что значит «нужные числа»? =)
Или я опять не понимаю вашего вопроса? Если так объясните что значит «нужные числа»? =)
Итак как и отвечал выше, для большинства задач того что сейчас есть вполне достаточно. Например в практической реализации алгоритма Диффи-Хеллмана (генерация общего секретного ключа без передачи его по каналам связи) советуется использовать числа порядка от 10^100 до 10^300. Очевидно, что ни одна нормальная программа не будет таскать с собой архив всех таких простых чисел (банально не хватит места) и генерирует их каждый раз заново. Т.е. таблицы простых чисел, как таковые, я полагаю, нигде не используются (разве, что в «спец-проектах»).
А достаточно конечно не намолотили, более того существуют достаточно внушительные денежные премии для энтузиастов-молотильщиков =).
А достаточно конечно не намолотили, более того существуют достаточно внушительные денежные премии для энтузиастов-молотильщиков =).
Для практического применения используется (на текущий момент) множество почти всех простых чисел размером до 4 тысяч бит (на число). При этом списка этих самых простых чисел ни у кого нет — их генерация и/или поиск начинается заново для каждого нового ключа шифрования.
Найти и составить список не получится по той причине, что не хватит места для записи даже для битовой маски — 2^4096 бит = 2^4092 байт = 4052 Тбайт.
Найти и составить список не получится по той причине, что не хватит места для записи даже для битовой маски — 2^4096 бит = 2^4092 байт = 4052 Тбайт.
Я когда-то давным давно еще в школьные годы использовал массив типа boolean в паскале на олимпиадах, что давало нереальный прирост скорости выполнения задач с простыми числами. Почему-то заполнить массив значениями true и false занимало считанные секунды, а вот вычисление, является ли конкретное число простым по другим алгоритмам было весьма долгим процессом.
В итоге у меня любые задачи класса «найти все такие простые числа, что..» выполнялись молниеносно, а у конкурентов вылетали за отведенное время.
Причины этого феномена я так и не изучил, а сейчас уже и поздно как-то, но к решету Эратосфена с тех пор отношусь с большим уважением.
В итоге у меня любые задачи класса «найти все такие простые числа, что..» выполнялись молниеносно, а у конкурентов вылетали за отведенное время.
Причины этого феномена я так и не изучил, а сейчас уже и поздно как-то, но к решету Эратосфена с тех пор отношусь с большим уважением.
если присмотреть в коде обнаруживается огромное количество ошибок, начиная с некоторых имен переменных которые сначала называются M а потом P, и кончая OutOfRange ошибками работы с массивами. Поправьте плиз чтобы было работоспособно.
Посмотрим на первый код. Говорят, что он нужен для того, чтобы найти простые до N <= 10^6. В таком случае в строке for (int j=i*i; j < N; j+=i) будет ошибка, так как j переполниться.
нет смысла разбирать ошибок слишком много… не важно… будем считать что человек хотел показать суть алгоритма
Sign up to leave a comment.
Волшебное решето Эратосфена