Здравствуйте. Как определить кол-во простых чисел от 1 до n с математической точки зрения, например от 1 до 10^9.

задан 18 Янв '14 0:26

изменен 20 Янв '14 19:54

Deleted's gravatar image


126

Чтобы найти точно это количество, нужно всё "честно" подсчитать -- "обходных" способов тут нет. Но для приблизительной оценки существует асимптотический закон распределения простых чисел. В отрезке от $%1$% до $%n$% таких чисел имеется порядка $%\frac{n}{\ln n}$%. При $%x\to\infty$% отношение числа $%\pi(x)$% (так стандартно обозначается количество простых чисел, не превосходящих $%x$%) к величине $%x/\ln x$% стремится к единице.

(18 Янв '14 0:33) falcao

Я не до конца понимаю постановку задачи. В частности, мне не ясна роль параметра $%k$%. Что он означает? Хотелось бы "чистого" описания на математическом языке, без "занимательного" сюжета и персонажей (мне трудно отсеивать ненужную информацию). Скорее всего, тут должно работать решето Эратосфена. Более сложных средств в такого рода задачах, как правило, не используется.

(18 Янв '14 1:19) falcao

Число является простым если оно не делится от 2 до k+1,решето Эратосфена здесь не подходит

(18 Янв '14 4:10) ivan145

Falcao,отвечаю про k. В условии задачи сказано, что год не должен быть простым, а он должен казаться главному герою простым, то есть не иметь простых делителей меньших k+2.Решето Эратосфена в этой задаче здесь не подходит,а вот как в этой задаче можно использовать метод включений-исключений на отрезке с учетом k

(18 Янв '14 21:15) ivan145

@ivan145: роль числа $%k$% я теперь понял. Решето Эратосфена, если я правильно понимаю, не подходит по той причине, что в худшем случае оно требует прохождения массива длиной $%10^9$%, а это считается много. Если это в самом деле так, то напрашивается идея использования формулы включений и исключений. Реализовать её, судя по всему, можно. Я попробую тогда изложить свои соображения.

(18 Янв '14 21:58) falcao

Отвечаю здесь, так как снизу всё исчерпано. Конечно, никаких произведений порядка $%10^{18}$% здесь в принципе возникнуть не может. Ведь рассматриваются только числа до $%10^9$%, и у них не бывает столь огромных делителей. Я уже говорил, что задача подсчёта для $%[A;B]$% сводится к нахождению разности $%f(B)-f(A-1)$%, то есть параметр в задаче фактически один: число $%n$% от $%1$% до $%10^9$%, для которого мы ищем $%f(n)$%.

(20 Янв '14 13:55) falcao

Falcao,я все реализовал,не считал те произведения которые больше 2*10^9,на тестах где k маленькое все проходит довольно неплохо,но в худшем случае при k=300,считает 3 секунды.Не может ли у этой задачи быть другого решения?

(25 Янв '14 10:41) ivan145
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
3

Попробую изложить реализацию одного из алгоритмов. Задачу я понимаю так. Нам даны три числа: $%A$%, $%B$% и $%k$%. Требуется найти количество чисел отрезка $%[A;B]$%, которые не делятся ни на одно простое число из отрезка $%[2;k+1]$%. Поскольку $%k$% сравнительно небольшое, мы можем быстро выписать все такие числа, пользуясь решетом Эратосфена. В худшем случае возникает список 2, 3, 5, ..., 293, в который входят 62 простых числа. Теперь надо реализовать функцию $%f(n)$%, которая подсчитывает количество чисел отрезка $%[1;n]$%, не делящихся ни на одно из указанных. Это будет некая процедура-функция, и далее она дважды вызывается, и вычисляется разность $%f(B)-f(A-1)$%. Число $%n$% может иметь порядок $%10^9$%.

Для подсчёта $%f(n)$% нужно узнать количество чисел, делящихся хотя бы на одно из наших простых. Пусть эти простые числа суть $%p_1 < \cdots < p_m$%. Количество чисел отрезка $%[1;n]$%, делящихся на $%p_i$%, нам известно, и оно вычисляется по формуле $%[n/p_i]$%, где квадратные скобки обозначают целую часть. В соответствии с формулой включений и исключений, все эти числа складываются. Далее из них надо вычесть величины, соответствующие попарным пересечениям, то есть $%[n/(p_ip_j)]$% при $%i < j$%. Потом прибавляются числа для тройных пересечений, и так далее.

Проблема в том, что пересечений, вообще говоря, имеется очень много, и в общем случае это будет величина порядка $%2^{62}$% (каждое простое число можно брать или не брать, составляя произведение различных простых). Однако у нас тут имеется ограничение чисел по величине, поэтому брать те произведения простых, которые превышают $%10^9$%, нам уже не надо. Соответственно, задача сводится к нахождению эффективного принципа перебора всех произведений различных простых из списка $%p_1,\ldots p_m$%, с условием, что произведение не превышает $%10^9$%.

Сделаем ещё вот какое замечание. Если нам надо подсчитать число $%[n/(st)]$%, то можно это сделать по формуле $%[[n/s]/t]$%, то есть округлять можно после каждого деления. Тогда составляем список чисел $%[n/p_1],[n/p_2],\ldots,[n/p_m]$%. Все эти числа складываем. Про каждое число мы запоминаем, на какое $%p_i$% мы его последний раз делили. Далее $%[n/p_1]$% делим с округлением на числа $%p_2,\ldots,p_m$%; число $%[n/p_2]$% делим с округлением на более "поздние" числа $%p_3,\ldots,p_m$% и так далее; $%[n/p_{m-1}]$% делим с округлением на $%p_m$%. Все полученные числа вычитаются. И далее повторяем эту процедуру, на каждом шаге меняя вычитание на сложение и наоборот, пока не произойдёт обнуление. Надо заметить, что количество действий тут не должно быть слишком большим: произведение первых 10 простых чисел уже превышает $%10^9$%, то есть делить слишком много раз будет не нужно. У самых больших простых чисел списка вообще берутся только три сомножителя. Судя по всему, этот план должен быть реализуем за предлагаемое время.

ссылка

отвечен 18 Янв '14 22:47

@falcao Думаю, что предложенное Вами решение действительно может уложится в ограничение времени. Но "Это будет некая процедура-функция, и далее она дважды вызывается, и вычисляется разность f(B)−f(A−1). Число n может иметь порядок $$10^9$$." В случае если А и В будут достаточно большими числами, а их разность небольшой, например, А=999999995 и В=999999999, то вместо проверки 4 чисел будут необоснованно дважды вычисляться значения функции для достаточно больших чисел. Уверен, что несколько тестов будут именно такого плана.

(19 Янв '14 0:18) aid78

Falcao,понял все до замечания.Является ли замечание еще одним способом решения задачи?или это продолжение того,что вы написали ранее?можно поконкретней о чем говорится в замечании.

(19 Янв '14 8:17) ivan145

@aid78: с Вашим замечанием я согласен. Но дело в том, что такого рода соображений может быть много, и они играют роль уже на стадии реализации программы. Она может себя вести как-то по-особому при "малых" значениях $%B$%, или $%B-A$%. У меня в первую очередь речь шла о преодолении чисто математических трудностей для "худшего" случая.

(19 Янв '14 9:34) falcao

@ivan145: замечание касалось способа вычисления целой части. Вместо $%[n/6]$% можно брать подсчитанное ранее значение $%[n/2]$%, которое далее делим на 3 с округлением вниз и получаем то же самое. Так удобнее реализовать алгоритм. Дальше у меня шло описание основной части, с формулой включений и исключений. Его было бы уместно начать с новой строки, так как это отдельная мысль, хотя и связанная с предыдущей. Фактически, это основной момент в вычислениях. Представьте себе формулу типа $%[n/p_1]+\ldots+[n/p_m]-([n/(p_1p_2]+[n/(p_1p_3)]+\ldots)+([n/(p_1p_2p_3)+\ldots)-$% и далее по тексту.

(19 Янв '14 9:40) falcao

Ага,это и есть формула включений и исключений,и вы говорите,что здесь можно сделать отсечение,что если произведение превысит 10^9,то уже это необязательно рассматривать.А почему это необязательно рассматривать?и не нарушит ли это итоговый ответ?

(19 Янв '14 10:00) ivan145

@ivan145: представьте себе формулу включений и исключений для этого случая в её полном виде. Если мы поделили $%n$% на очень большое число, то целая часть такого частного равна нулю. Поэтому слагаемые этого вида можно не рассматривать. Мы ведь по формуле $%[n/s]$% подсчитываем количество чисел от 1 до $%n$%, кратных $%s$%, но в случае $%s > 10^9$% таких чисел просто нет.

(19 Янв '14 10:13) falcao

Да с таким отсечением согласен,но есть проблема.Допустим нам достался худший случай и чисел простых будет 62.И когда (n/(p1p2p3p4p5p6p7p8p9p10)+n/(p1p2p3p4p5p6p7p8p9p11))и т.д. в фор-ле включений и исключений то этот перебор комбинаций займет слишком много времени,если составлять комбинации по 2,3,4,5 то это еще проходит,возможно пройдет и по 6,но когда составляем комбинации из 62 чисел по семь,то тут уже начинаются проблемы.Возможно ли это как-то избежать?

(20 Янв '14 12:53) ivan145

@ivan145: здесь не надо составлять все комбинации (сочетания) из 62 по 7. Учитывать и рассматривать надо только те произведения простых, которые не превосходят $%10^9$%. Их относительно немного, и "отсев" происходит на достаточно ранней стадии. Я показал, как можно осуществить перебор при помощи составления списков. Об этом в последнем абзаце говорится. Суть в том, что "длинных" произведений в списке будет очень мало.

(20 Янв '14 13:11) falcao

Ага,понял,и еще кое-что по условию задачи a<=10^9 и b<=10^9 а это означает рассматривать надо только те произведения простых которые не превосходят 10^18 или я не прав?

(20 Янв '14 13:37) ivan145
показано 5 из 9 показать еще 4
10|600 символов нужно символов осталось
3

В условии задачи сказано, что год не должен быть простым, а он должен казаться главному герою простым, то есть не иметь простых делителей меньших k+2. Решето Эратосфена от 2 до k+1 здесь должно подойти. Его реализацию на любом распространенном алгоритмическом языке не сложно найти с сети. А если будет лимит времени, то сделайте отдельную программу, которая будет заполнять массив логических переменных от 1 до 10^9 по принципу true если число не имеет делителей меньших k+2 и false в противном случае. В ту программу, что будете тестировать внесите этот массив как массив констант и в самой программе считайте сколько true попало от A до B.

ссылка

отвечен 18 Янв '14 10:00

Извините,но я уже это пробывал,слишком много памяти выделяется,поэтому этот вариант отпадает

(18 Янв '14 21:16) ivan145

@ivan145: приходится отвечать здесь. Я посмотрел в условие, и там, насколько я понимаю, $%B$% играет роль количества чисел отрезка, то есть найти надо то, что попадает в $%[A;A+B]$%. Сути дела это не меняет, так как слегка изменяется ограничение: получается $%2\cdot10^9$%, то есть величина того же порядка, что и была. Разумеется, никакого $%10^{18}$% тут нет и быть не может: ведь числа $%A$% и $%B$% всего лишь складываются, а не перемножаются.

(20 Янв '14 14:43) falcao

@ivan145: я говорил, что не надо считать через $%C_{62}^7$%. Ясно, что это очень большое число (порядка половины миллиарда). У меня был описан другой алгоритм, основанный на составлении списков. Я могу попробовать сегодня вечером его реализовать в Maple чисто ради спортивного интереса. Вариантов там не должно быть слишком много.

(21 Янв '14 16:45) falcao

@ivan145: я пришёл к этому выводу на основании того, какие именно члены надо учитывать в формуле включений и исключений. Они именно такие, как я описал. Понятно, что каждое из них учитывать нужно в силу вида формулы. То есть надо работать со списками, учитывая то, на что мы уже делили, чтобы не повторить дважды то же самое. А привлекать сочетания тут незачем, потому что очень многие произведения 7 сомножителей слишком велики. Кроме того, сам алгоритм перебора сочетаний, если его реализовать, превратится примерно в то же самое.

(21 Янв '14 19:33) falcao

Насколько я понимаю,это почти тоже самое,что и перебор сочетаний,но убыстренный в силу того,что мы запоминаем предущие вычисления

(21 Янв '14 19:42) ivan145

@ivan145: я делаю похоже, но немного не так. На каждом шаге мы храним списки чисел. На нулевом шаге есть список из числа n. Скажем, что оно имеет ранг 0. Это число идёт с плюсом при вычислении ответа. Далее возникает m списков из одного числа каждый: $%n/p_1$%; ... ; $%n/p_m$%. Этим числам присваиваем ранги от 1 до m. Это всё идёт с минусом. На следующем шаге возникают списки: $%n/(p_1p_2)$% (ранг 2), $%n/(p_1p_3)$%, $%n/(p_2p_3)$% (ранг 3), ..., $%n/(p_1p_m)$%, ..., $%n/(p_{m-1}p_m)$% (ранг m). Знаки всё время меняются; рангом считается наибольший номер i, если делили на $%p_i$%.

(21 Янв '14 23:33) falcao

для n/(pm-1pm) понятно как будет выглядеть алгоритм,а как он будет выглядеть когда делим n на три элемента?И как мы эти числа все время будем запоминать с этим тоже проблема,ведь их становится все больше и больше

(22 Янв '14 11:27) ivan145
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×4,869

задан
18 Янв '14 0:26

показан
5129 раз

обновлен
25 Янв '14 10:41

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru