Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 50
Во-первых, не верю про гигабайт и килобайт, речь явно об асимптотике. Тем более, если надо хранить простые числа, то сложновато уложиться в такой объем памяти :) Во-вторых, хотелось бы больше деталей об алгоритме. Описание выглядит весьма непонятно, да и временной оценки даже нет.
А еще более интересно узнать реальные результаты. Это, конечно, здорово, что найден такой алгоритм, но что-то мне подсказывает, что он чертовски медленный на практике.
Кстати, блочное решето Эратосфена требует всего sqrt(N) памяти. Этого достаточно, чтоб считать простые числа хоть до 10 в 18й в гигабайтах памяти, плюс можно обрабатывать только нужные окна. Неясно, умеет ли этот новый алгоритм такое. А для совсем больших чисел проще использовать какой-нибудь тест на простоту, всяко быстрее будет.
А еще более интересно узнать реальные результаты. Это, конечно, здорово, что найден такой алгоритм, но что-то мне подсказывает, что он чертовски медленный на практике.
Кстати, блочное решето Эратосфена требует всего sqrt(N) памяти. Этого достаточно, чтоб считать простые числа хоть до 10 в 18й в гигабайтах памяти, плюс можно обрабатывать только нужные окна. Неясно, умеет ли этот новый алгоритм такое. А для совсем больших чисел проще использовать какой-нибудь тест на простоту, всяко быстрее будет.
там гигабайт и мегабайт.
Although reducing the space requirement generally implies certain “minor” sacrifices in the theoretical speed of the algorithm, Helfgott believes that in certain ranges the deficit could be offset or exceeded by the possibility of mainly or exclusively using the cache memory—which is smaller but faster than main memory or RAM. “It depends on the application,” he says.
В теперешней модели CPU эффективность работы во многом упирается в чтение из памяти. Разница между поместились все данные в кеш процессора или нет может быть радикальна.
В блочном решете нужно не менее O(n^(1/2)) бит памяти. А в приведенном алгоритме O(n^(1/3) * log(n)^(2/3)). Ясно, что вероятность попадания в кеш должна быть больше у нового алгоритма при достаточно больших n. К тому же он имеет O(n) по времени: «y tiempo aun esencialmente linear en N».
На счет линейного времени интересно. Что-то мне кажется, что это уже не решето Эратосфена :)
Дополнительный log, кстати, весьма портит картину. Для миллиарда, например, разница всего в 4 раза (допуская одинаковую константу, а я почти уверен, что константа больше). Ну а дальше уже ни о каком кэше речи нет и алгоритм упирается в другие проблемы.
Короче, имхо, очередное занятное теоретическое достижение, которое мы вряд ли увидим в практике.
Дополнительный log, кстати, весьма портит картину. Для миллиарда, например, разница всего в 4 раза (допуская одинаковую константу, а я почти уверен, что константа больше). Ну а дальше уже ни о каком кэше речи нет и алгоритм упирается в другие проблемы.
Короче, имхо, очередное занятное теоретическое достижение, которое мы вряд ли увидим в практике.
Кстати, блочное решето Эратосфена требует всего sqrt(N) памяти.
Ну так называемое блочное решето это лишь оптимизация реализации существующего алгоритма. А здесь, как я понимаю речь идет именно о оптимизации на фундаментальном уровне.
Вообще интересно было бы взглянуть на улучшенный алгоритм и поиграться на практике.
«Как и многие другие 10-летние дети, я изучал решето Эратосфена в начальной школе», — говорит Харальд Хельфготт
А вот сейчас обидненько было.
Может он только перуанских детей имел в виду? Мало ли что они там в 4-5 классах по математике изучают. :)
А вот сейчас обидненько былоПлан-конспект урока (6 класс) по теме:
Конспект урока «Простые и составные числа. Решето Эратосфена»
Только 6 класс — это 12 — 13 лет.
Вы слишком буквально смотрите на циферки. Человеку 40 лет. Думаете он четко помнит — 10, 11.5 или 12?
Ну… у всех по-разному. Я 84-го года (конец августа), в 6-й класс пошел в 94-м году, ровно в 10 лет. Так что вполне человек может не врать. Я тоже в 10 лет проходит решето Эратосфена.
В 5 лет в школу пошли? Это довольно редкое исключение из правил. Я в 3 года читать научился, но сказать «как и многие другие дети трёхлетнего возраста» было бы о-о-очень большим преувеличением :)
Нет, почему же, в 6.
1990 (6 лет) — 1 класс
1991 (7 лет) — 2 класс
1992 (8 лет) — 3 класс
1993 (9 лет) — 5 класс
1994 (10 лет) — 6 класс
В гимназиях (и не только) в 90-х 4-й класс почти всегда перепрыгивали.
1990 (6 лет) — 1 класс
1991 (7 лет) — 2 класс
1992 (8 лет) — 3 класс
1993 (9 лет) — 5 класс
1994 (10 лет) — 6 класс
В гимназиях (и не только) в 90-х 4-й класс почти всегда перепрыгивали.
Тогда это не 6-й класс, а 5-й фактически. По ссылке нынешняя программа и по ней не перескакивают.
А вы точно помните, что именно в том году вы изучли «решето»? А то, вон, люди сверху считают, что это невозможно запомнить :)
Да, и 6 лет — тоже не правило, а исключение.
А вы точно помните, что именно в том году вы изучли «решето»? А то, вон, люди сверху считают, что это невозможно запомнить :)
Да, и 6 лет — тоже не правило, а исключение.
Точно не в 3-ем, поэтому точно в 5-ом )
В школе оно немного иначе проходится: натуральные числа пишутся в столбец (по 3 в каждом ряду) и обводятся в кружочки в цикле каждое 2 и 4 числа, начиная с 5 (2 и 3 в виде исключения тоже). Остальные считаются вычеркнутыми. Получается: 5, 7, 11, 13, 17, 19, 23 (и т. д.).
И на счет 4-го вы ошибаетесь. 3-ий класс = 4 классу. Раньше программа иная была. В гимназиях успешное завершение 9-ого класса приравнивается по основной программе к завершению 11-го общеобразовательного.
Другими словами, программа 1-4 класс проходится за 3 года, затем программа 5-11 класс еще за 5 лет. Следующие 2 года идет расширенная программа + предвузовская подготовка.
В школе оно немного иначе проходится: натуральные числа пишутся в столбец (по 3 в каждом ряду) и обводятся в кружочки в цикле каждое 2 и 4 числа, начиная с 5 (2 и 3 в виде исключения тоже). Остальные считаются вычеркнутыми. Получается: 5, 7, 11, 13, 17, 19, 23 (и т. д.).
И на счет 4-го вы ошибаетесь. 3-ий класс = 4 классу. Раньше программа иная была. В гимназиях успешное завершение 9-ого класса приравнивается по основной программе к завершению 11-го общеобразовательного.
Другими словами, программа 1-4 класс проходится за 3 года, затем программа 5-11 класс еще за 5 лет. Следующие 2 года идет расширенная программа + предвузовская подготовка.
>Точно не в 3-ем, поэтому точно в 5-ом )
Почему не в 6-ом тогда?
>В гимназиях успешное завершение 9-ого класса приравнивается по основной программе к завершению 11-го общеобразовательного.
То есть после девятого можно было поступать в вуз? И с какой тогда целью было тратить на гимназию ещё два года? Бессмыслица какая-то.
Насколько я помню, всё было иначе. Вместо 10-летки ввели 11-летку, а программу не переработали. Поэтому долгое время учились по старой советской программе, просто пропуская в нумерации 4-й класс.
Почему не в 6-ом тогда?
>В гимназиях успешное завершение 9-ого класса приравнивается по основной программе к завершению 11-го общеобразовательного.
То есть после девятого можно было поступать в вуз? И с какой тогда целью было тратить на гимназию ещё два года? Бессмыслица какая-то.
Насколько я помню, всё было иначе. Вместо 10-летки ввели 11-летку, а программу не переработали. Поэтому долгое время учились по старой советской программе, просто пропуская в нумерации 4-й класс.
Потому, что тема простых чисел идет сразу же с темой деления (какие числа делятся только на 1 и самих себя), а умножение и деление мы проходили в 5-ом классе. Это раз.
Второе: моя дочь в прошлом году закончила 5-ый класс, и в середине года мы проходили с ней то же деление, умножение, простые числа, остаток от деления, НОК, НОД и в конце дроби. Т.е. до сих пор простые числа идут в 5 классе (школа обычная).
Далее, по поводу перехода от 10-летки к 11-летке вы абсолютно правы. Но это касается только 1-4 классы за 3 года. Поэтому это не имеет отношения к разнице в программах гимназий и средних школ.
Последний вопрос — зачем в гимназиях 11 классов тогда. Не все программы сжаты до 9 класса. Например, литература идет по стандартной программе, т.к. не каждый ребенок в 11 классе может хоть что-то понять из классики, что говорить о детях на 2 года младше. В 10 и 11 классах обычно очень много выездных лабораторных работ (обычно в ВУЗы) и ВУЗовских преподавателей на расширенной программе в самой школе.
Второе: моя дочь в прошлом году закончила 5-ый класс, и в середине года мы проходили с ней то же деление, умножение, простые числа, остаток от деления, НОК, НОД и в конце дроби. Т.е. до сих пор простые числа идут в 5 классе (школа обычная).
Далее, по поводу перехода от 10-летки к 11-летке вы абсолютно правы. Но это касается только 1-4 классы за 3 года. Поэтому это не имеет отношения к разнице в программах гимназий и средних школ.
Последний вопрос — зачем в гимназиях 11 классов тогда. Не все программы сжаты до 9 класса. Например, литература идет по стандартной программе, т.к. не каждый ребенок в 11 классе может хоть что-то понять из классики, что говорить о детях на 2 года младше. В 10 и 11 классах обычно очень много выездных лабораторных работ (обычно в ВУЗы) и ВУЗовских преподавателей на расширенной программе в самой школе.
>Второе: моя дочь в прошлом году закончила 5-ый класс, и в середине года мы проходили с ней то же деление, умножение, простые числа, остаток от деления, НОК, НОД и в конце дроби. Т.е. до сих пор простые числа идут в 5 классе (школа обычная).
То есть по приведённой ссылке — ложь?
>Не все программы сжаты до 9 класса.
Ну, так я про вашу «сжатую» спрашиваю. Какой смысл оставаться там после 9-го, если можно сразу поступать в вуз? А если планов поступления нет, то тем более.
То есть по приведённой ссылке — ложь?
>Не все программы сжаты до 9 класса.
Ну, так я про вашу «сжатую» спрашиваю. Какой смысл оставаться там после 9-го, если можно сразу поступать в вуз? А если планов поступления нет, то тем более.
Возможно, ваша ссылка на авторскую программу или программу для 12-летки.
Если вы в гугл вобьете «простые числа 5 класс», увидите кучу материалов.
По второму вопросу я ответил, вы просто не так поняли. В сжатой программе не все предметы сжимаются, а примерно половина — две трети. Есть предметы, которые сжать нельзя, и они идут по стандартной программе. А освободившееся время от сжатия части программы используется для ее расширения.
Если вы в гугл вобьете «простые числа 5 класс», увидите кучу материалов.
По второму вопросу я ответил, вы просто не так поняли. В сжатой программе не все предметы сжимаются, а примерно половина — две трети. Есть предметы, которые сжать нельзя, и они идут по стандартной программе. А освободившееся время от сжатия части программы используется для ее расширения.
>Возможно, ваша ссылка на авторскую программу или программу для 12-летки.
Если вы в гугл вобьете «простые числа 5 класс», увидите кучу материалов.
Не, может ваша программа — авторская? :)
Куча материалов представляет собой в основном не планы урока про решето, а «проекты» учеников, то есть то, что сверх программы. А программно в основном как раз 6-е классы встречаются. Но один вариант с пятым тоже нашёлся, да.
Впрочем, это не так важно. Видимо, оба варианта есть.
>По второму вопросу я ответил, вы просто не так поняли
Видимо не так. То есть после 9-го в вуз всё-таки нельзя? Тогда 9-й НЕ эквивалентен полному среднему образованию, а эквивалентен советским 8-м классам — неполное среднее. После него не вуз, а в ПТУ/техникум — в совке или колледж, лицей, (не знаю что ещё) — современной терминологии — дополучать образование до среднего специального или среднего профессионального. В таком варианте всё логично и ни чем не отличается по сути от старого. А расширения программы, ну они всегда были. Только называлось это не гимназиями, а спецшколами.
Если вы в гугл вобьете «простые числа 5 класс», увидите кучу материалов.
Не, может ваша программа — авторская? :)
Куча материалов представляет собой в основном не планы урока про решето, а «проекты» учеников, то есть то, что сверх программы. А программно в основном как раз 6-е классы встречаются. Но один вариант с пятым тоже нашёлся, да.
Впрочем, это не так важно. Видимо, оба варианта есть.
>По второму вопросу я ответил, вы просто не так поняли
Видимо не так. То есть после 9-го в вуз всё-таки нельзя? Тогда 9-й НЕ эквивалентен полному среднему образованию, а эквивалентен советским 8-м классам — неполное среднее. После него не вуз, а в ПТУ/техникум — в совке или колледж, лицей, (не знаю что ещё) — современной терминологии — дополучать образование до среднего специального или среднего профессионального. В таком варианте всё логично и ни чем не отличается по сути от старого. А расширения программы, ну они всегда были. Только называлось это не гимназиями, а спецшколами.
Я предлагаю вернуться к тому, с чего начали. Тезис «Как и многие другие 10-летние дети, я изучал решето Эратосфена в начальной школе».
«Как и многие 10-летние дети» — согласен, тут не сказано, что все, по всему миру вполне вероятно, что многие.
«В начальной школе» — вот тут у меня серьезные сомнения, т.к. начальная школа — это ДО 5 класса. 5-й класс — это уже средняя школа. Я не нашел ни одной программы изучения решета Эратосфена в 3-х или 4-х классах.
«Как и многие 10-летние дети» — согласен, тут не сказано, что все, по всему миру вполне вероятно, что многие.
«В начальной школе» — вот тут у меня серьезные сомнения, т.к. начальная школа — это ДО 5 класса. 5-й класс — это уже средняя школа. Я не нашел ни одной программы изучения решета Эратосфена в 3-х или 4-х классах.
Вы про какую страну? В англии элементари скул до 11 (а было до 14), в штатах до 12. В странах с двухстадийным образованием (праймери, секондари), праймери, как правило, тоже до 12. В нашей начальной, да, не изучают. Именно поэтому человек и сказал — обидненько за наше, якобы, самое лучшее образование.
Программа обучения везде разная, и меняется в зависимости от автора учебника. (очень много знакомых в системе образования, знаю о чем говорю). У кого то тема с простыми числами в 5 классе, у кого то 7. Например, в лицее, где я учился матрицы изучались в 7 классе, хотя обычно их изучают только в ВУЗе.
Кстати, тоже 84 г.р.
1991 (6 лет) — 1 и 2 класс за 1 год
1992 (7 лет) — 3 класс
1993 (8 лет) — 5 класс
1994 (9 лет) — 6 класс
1995 (10 лет) — 7 класс
1996 (11 лет) — 8 класс
1997 (12 лет) — 9 класс
1998 (13 лет) — 10 класс
Остался бы на последний год в гимназии — окончил бы школу в 15.
1991 (6 лет) — 1 и 2 класс за 1 год
1992 (7 лет) — 3 класс
1993 (8 лет) — 5 класс
1994 (9 лет) — 6 класс
1995 (10 лет) — 7 класс
1996 (11 лет) — 8 класс
1997 (12 лет) — 9 класс
1998 (13 лет) — 10 класс
Остался бы на последний год в гимназии — окончил бы школу в 15.
6 класс это 12 лет
Перу. Дикари.
Лично я встречал оное решето в своём учебнике по математике за третий класс (1992 год, москва). И даже вроде бы понял. Только, во-первых, оно там отчего-то называлось решетом Евклида, а во-вторых, на уроках мы его так и не прошли. А ещё там комплексные числа упоминались, но как-то вскользь.
Виноградов доказал не от 1 до N, а от N до бесконечности. Т.е. чтобы доказать тернарную гипотезу полностью, можно было бы просто проверить руками или на компьютере от 1 до N, если бы не астрономическое число N.
upd. Собственно, Хельфготт доказал тернарную гипотезу снизив границу N до не настолько большого числа, а все числа до N добил с помощью компьютера.
upd. Собственно, Хельфготт доказал тернарную гипотезу снизив границу N до не настолько большого числа, а все числа до N добил с помощью компьютера.
а кто-нибудь следит за последними достижениями в области факторизации? что-то удачное за последние 10 лет придумали для ускорения факторизации?
А какой смысл искать простые числа?
Ребят, а можете пару слов сказать вот об этом моменте, пожалуйста?
«Советские математики думали, что Виноградов доказал гипотезу для всех чисел, но на самом деле позже выяснилось, что граница N в работе Виноградова составляет 10^6 846 168.»
Википедия говорит, что Виноградов говорил о «достаточно большом нечётном числе», а его студент дал нижнюю границу этого числа. Что это означает? Что студент для этого числа посчитал справедливость гипотезы?
«Советские математики думали, что Виноградов доказал гипотезу для всех чисел, но на самом деле позже выяснилось, что граница N в работе Виноградова составляет 10^6 846 168.»
Википедия говорит, что Виноградов говорил о «достаточно большом нечётном числе», а его студент дал нижнюю границу этого числа. Что это означает? Что студент для этого числа посчитал справедливость гипотезы?
28 сентября 2016 в 08:32 пользователь ripatti написал:
Виноградов доказал не от 1 до N, а от N до бесконечности. Т.е. чтобы доказать тернарную гипотезу полностью, можно было бы просто проверить руками или на компьютере от 1 до N, если бы не астрономическое число N.
upd. Собственно, Хельфготт доказал тернарную гипотезу снизив границу N до не настолько большого числа, а все числа до N добил с помощью компьютера.
А где можно ознакомиться с описанием этого алгоритма? Ни одна из ссылок в материале не ведет куда-то, кроме новостных сайтов без деталей.
Тоже руки чешутся реализовать.
Я нашел его комментарий по этой теме на slashdot, но без подробностей. Люди в публикации ссылаются на вот этот препринт, но я еще не смотрел его на предмет, можно ли из него извлечь достаточно данных для формального описания алгоритма.
Теперь понятно. Собственно, потому и вопрос был, что 10^6846168 — это что-то за гранью понимания вообще.
После прочтения а что такое число грема вот там точно за гранью понимания… 10^6846168 это вообще мелочи ))
После прочтения а что такое число грема вот там точно за гранью понимания… 10^6846168 это вообще мелочи ))
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Математик оптимизировал решето Эратосфена, чтобы искать простые числа с меньшим расходом памяти