Вывести количество простых чисел на интервале

@Overlord Cows · Регистрация: 25.12.2021

Студворк — интернет-сервис помощи студентам

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var 
   i, a, b, n, s: integer;
begin
   Read(a);
   Read(b);
   a := a - 1;
   b := b - 1;;
   s := 0;
   Repeat
   a := a + 1;
   n := 0;;
   for i := 2 to trunc(a/2) + 1 do
      if a mod i = 0 then 
         n := n + 1;
   if n = 0 then 
      s := s + 1;
   until (a > b);
   Writeln(s);
end.

@Cyborg Drone · 13.03.2022, 00:24

И что не так с этой далеко не оптимальной программой?

@Overlord Cows · 13.03.2022, 19:50 **[ТС]**

Не проходит по времени

Добавлено через 23 минуты
К тому же не везде верный ответ выводит

@Cyborg Drone · 14.03.2022, 01:14

Понятно. А что, сразу написать религия не позволила? Правило форума:

4.7. Как можно более полно описывайте суть проблемы или вопроса, что было сделано для ее решения и какие результаты получены.

На выяснение того, а что же Вы желаете на самом деле, уходит дополнительное время. Если бы Вы сразу оформили тему как нормальный человек, а не как ленивый неуч, Вы бы получили ответ сутки назад.

Естественно, Ваша программа не проходит по времени, поскольку до жути не оптимальная. Хуже, чем у Вас, это проверять все делители для каждого числа, от 1 до самого числа. А ведь достаточно найти только один делитель, чтобы понять, что число составное.

Ваша программа не проходит все тесты потому, что она числа, меньшие 2, ошибочно считает простыми.

Известно, что натуральное число может быть простым тогда и только тогда, когда оно равно 2 или 3, или его можно выразить формулой n=6k±1, где k - натуральное число. Среди других чисел простых нет. Программу сразу можно ускорить в три раза, поскольку нужно будет проверять только два числа из шести. Отсеивание чисел, делящихся на 2 или на 3, дополнительно ускорит программу.

Каждый делитель числа имеет пару. Если число n делится на t, то оно по понятной причине делится и на (n div t). Таким образом, при проверке простоты числа достаточно искать делители от 2 до корня квадратного из числа, поскольку меньший делитель из пары не может превосходить корень квадратный из числа. Это куда быстрее, чем перебирать делители до n div 2. Если делители в указанном диапазоне не найдены, то число простое.

Лучше всего искать только те делители, которые сами являются простыми числами. В этом случае придётся заранее найти все возможные простые делители (чтобы не искать их всякий раз заново), но, так как верхняя граница диапазона не определена заранее, и может быть очень большой, то и размер массива простых делителей получается также неопределённым и большим. Медленнее, но проще: можно искать не простые делители, а делители, которые могут быть простыми, то есть, по тому же принципу 2, 3, 6k±1.

Предлагаю в диапазоне [a; b], где a ≤ b, проверять простоту только чисел вида 6k±1, которые не делятся на 2 или на 3. Делители каждого числа будем искать до корня из числа, набор делителей - 2, 3, 6k±1. Поиск делителей будем прерывать при нахождении первого попавшегося делителя (составное число), или если предполагаемый делитель превысил корень из числа (простое число). Числа вида 6k±1 будем искать так: находим первое такое число, а потом прибавляем к нему то 2, то 4.

Для сдачи на проверочный сайт:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
var
  a, b, da, d, dd, sq, k: integer;
begin
  readln(a, b); //вводим диапазон чисел
  if a >= 5 then //корректируем a, определяем начальное приращение
    begin
      k := 0; //количество найденных чисел пока 0
      inc(a, (5 - a mod 6) mod 4); //первое число вида 6k+-1, не меньшее a
      if a mod 6 < 2 then da := 4 else da := 2 //первое приращение числа
    end
  else //при a<5 дополнительно учитываем a=2, a=3 и b<3
    begin
      if b < 2 then k := 0
      else
        if b = 2 then k := 1
        else
          if a <= 2 then k := 2
          else k := a and 1;
      a := 5; //первое число вида 6k+-1, большее a
      da := 2 //первое приращение числа
    end;
  while a <= b do //ищем простые
    begin
      if a mod 3 <> 0 then //замечание: 6k+-1 не делится на 2
        begin //если число не делится на 3, то
          sq := trunc(sqrt(a)); //определяем целую часть корня из числа
          d := 5; //первый делитель вида 6k+-1
          dd := 2; //начальное приращение делителя
          while (d <= sq) and (a mod d <> 0) do
            begin //пока делитель не больше корня, и число не делится на него
              inc(d, dd); //вычисляем следующий делитель
              dd := dd xor 6 //вычисляем следующее приращение делителя (то 2, то 4)
            end;
          if d > sq then inc(k) //если делители не найдены, то число простое
        end;
      inc(a, da); //вычисляем следующее число
      da := da xor 6 //вычисляем следующее приращение числа (то 2, то 4)
    end;
  writeln(k) //печатаем результат
end.

Если а ≥ 5, то программу можно существенно укоротить.

Разбирайтесь.

Если нужно ещё быстрее, то укажите максимально возможное b, попробуем искать все возможные делители заранее.

Добавлено через 23 минуты
На всякий случай, медленнее, но проще (но всё равно значительно быстрее, чем у Вас), на простоту проверяются все числа, не делящиеся на 2, с помощью перебора нечётных делителей от 3 до корня из числа:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var
  a, b, d, sq, k: integer;
begin
  readln(a, b); //вводим диапазон
  k := 0;
  if a <= 2 then
    begin
      inc(k); //учитываем a=2
      a := 3 //первое нечётное простое число
    end
  else a := a or 1; //первое нечётное число, не меньшее a
  while a <= b do //ищем простые
    begin
      sq := trunc(sqrt(a)); //определяем целую часть корня из числа
      d := 3; //первый нечётный делитель
      while (d <= sq) and (a mod d <> 0) do inc(d, 2); //ищем делители
      if d > sq then inc(k); //если делители не найдены, то число простое
      inc(a, 2) //вычисляем следующее число
    end;
  writeln(k) //печатаем результат
end.

@Overlord Cows · 14.03.2022, 07:28 **[ТС]**

Максимальный b 10^12

@bormant · 14.03.2022, 17:05

Cyborg Drone,
строго говоря, [1,1] должно давать 0.

@Cyborg Drone · 14.03.2022, 23:00

bormant, это я дооптимизировался. Не помню уже, как было до оптимизации, попытаюсь восстановить... Так, кажется:

Pascal
5
6
7
8
9
10
11
  if b < 2 then k := 0
  else
    if b = 2 then k := 1
    else
      if a < 3 then k := 1
      else k := 0;
  if a < 3 then a := 3 else a := a or 1;

Overlord Cows, для начала поменять в программах из сообщения #4 все integer на int64.

Хорошо хоть 10¹², а не 10¹¹², но, всё равно, получается непросто. При такой верхней границе спасёт только решето Аткина, быстрее него ничего в мире нет. Если честно, то всё же есть, может быть, даже чуть быстрее, но со значительно большими размерами требуемой памяти.

Материалы по теме (чтобы потом не искать):
A. O. L. Atkin and D. J. Bernstein - Prime sieves using binary quadratic forms
Wikipedia - Sieve of Atkin
Википедия - Решето Аткина
Хабр - Еще раз о поиске простых чисел
Wikipedia - Wheel factorization
Wikipedia - Square-free integer

Ещё раз уточните задание:
- в каких пределах могут быть обе границы диапазона, и a, и b;
- какой лимит по времени;
- какой лимит по памяти;
- какой диалект паскаля.

@Overlord Cows · 14.03.2022, 23:22 **[ТС]**

Ограничения 2<=a<=b<=10^12
Лимит по времени: 2 сек
Лимит по памяти: 65536 кбайт
PascalABC.NET

Добавлено через 8 минут
В общем, мне сказали что я дурачок, что выбрал эту задачу, так как она мега сложная, можете не напрягаться, решить на паскале ее практически нереально, простите (

@Cyborg Drone · 15.03.2022, 00:27

Скажете тоже, "нереально"... Не такая уж эта задача и мегасложная. Считать будет только сравнительно долго, и память жрать, как крокодил.

Сложность здесь не в написании программы. Вложиться в лимит по времени и в лимит по памяти, скорее всего, не удастся на любом языке программирования, вот в чём засада: для интервала [2; 10¹²] при использовании быстрейшего в мире алгоритма поиска простых чисел на паскале или C++ по времени навскидку получится секунд пять, если компьютер на сервере не из прошлого века, а по памяти при приемлемом времени получается порядка sqrt(10¹²)=1000000 байт. Если использовать BitPacking, то можно обойтись 125000 байтами, но программа будет чуть медленнее.

Не напишешь - не узнаешь. А попробую написать.

Конечно, на Pascal ABC.NET с его JIT-компилятором побыстрее будет, вот только на проверочных сайтах частенько пишут "Pascal ABC.NET", а на самом деле там крутится не самый новый Free Pascal на каком-нибудь Ubuntu.

Адрес проверочного сайта приведите.

@bormant · 15.03.2022, 08:57

Сообщение от Cyborg Drone

Считать будет только сравнительно долго

... но если предвычислить количество простых на крупных интервалах, останется довычислять только "хвосты"...
Против лома нет приема

Добавлено через 8 минут
Те, что не влезли в LongWord, можно хранить как дополнение к Base (Base+BigPrime[i]), что позволит не увеличивать вдвое необходимую память.

Добавлено через 33 минуты
Еще про возможный вариант хранения таблицы простых:
https://habr.com/ru/post/417753/

Новые блоги и статьи Все статьи Все блоги /
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ
Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .	Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .

@Cyborg Drone Модератор 10451 / 5742 / 3409 Регистрация: 17.08.2012 Сообщений: 17,476
	13.03.2022, 00:24
	И что не так с этой далеко не оптимальной программой? 0

@Overlord Cows 0 / 0 / 0 Регистрация: 25.12.2021 Сообщений: 39
	13.03.2022, 19:50 [ТС]
	Не проходит по времени Добавлено через 23 минуты К тому же не везде верный ответ выводит 0

@Overlord Cows 0 / 0 / 0 Регистрация: 25.12.2021 Сообщений: 39
	14.03.2022, 07:28 [ТС]
	Максимальный b 10^12 0

@bormant Модератор 7816 / 4635 / 2837 Регистрация: 22.11.2013 Сообщений: 13,159 Записей в блоге: 1
	14.03.2022, 17:05
	Cyborg Drone, строго говоря, [1,1] должно давать 0. 0

@Overlord Cows 0 / 0 / 0 Регистрация: 25.12.2021 Сообщений: 39
	14.03.2022, 23:22 [ТС]
	Ограничения 2<=a<=b<=10^12 Лимит по времени: 2 сек Лимит по памяти: 65536 кбайт PascalABC.NET Добавлено через 8 минут В общем, мне сказали что я дурачок, что выбрал эту задачу, так как она мега сложная, можете не напрягаться, решить на паскале ее практически нереально, простите ( 0

@Cyborg Drone Модератор 10451 / 5742 / 3409 Регистрация: 17.08.2012 Сообщений: 17,476
	15.03.2022, 00:27
	Скажете тоже, "нереально"... Не такая уж эта задача и мегасложная. Считать будет только сравнительно долго, и память жрать, как крокодил. Сложность здесь не в написании программы. Вложиться в лимит по времени и в лимит по памяти, скорее всего, не удастся на любом языке программирования, вот в чём засада: для интервала [2; 10¹²] при использовании быстрейшего в мире алгоритма поиска простых чисел на паскале или C++ по времени навскидку получится секунд пять, если компьютер на сервере не из прошлого века, а по памяти при приемлемом времени получается порядка sqrt(10¹²)=1000000 байт. Если использовать BitPacking, то можно обойтись 125000 байтами, но программа будет чуть медленнее. Не напишешь - не узнаешь. А попробую написать. Конечно, на Pascal ABC.NET с его JIT-компилятором побыстрее будет, вот только на проверочных сайтах частенько пишут "Pascal ABC.NET", а на самом деле там крутится не самый новый Free Pascal на каком-нибудь Ubuntu. Адрес проверочного сайта приведите. 1

Вывести количество простых чисел на интервале

Решение