Модуль: ЕГЭ-2022. Вопрос 25. Поиск делителей


Задача

4 /11


Простые числа

Теория Нажмите, чтобы прочитать/скрыть


Простые числа

Простое число - это число, которое делится только на 1 и на само себя. 1 не считается простым числом. Поэтому, любое простое число имеет только 2 делителя.
Используя оптимальный алгоритм подсчета числа делителей, можно сказать, что просто число не имеет делителей на промежутке от 2 до \(\sqrt n\). Таким образом, достаточно перебрать возможные делители на диапазоне \([2; \sqrt n ]\) и если на этом диапазоне нет делителей, то их не будет и на диапазоне \([ \sqrt n + 1; n -1]\)

Фрагмент программы, который выводит на экран информацию о том, простое число n или составное будет выглядеть так:
 

C++

Python Pascal
int k = 0, i = 2;
  while (i * i <= n)
  {
      if (n % i == 0)
      {
          k++;   
          break;
    }
    i += 1;  
  }
  if (k == 0)
    cout << "Число простое";
  else
    cout << "Число составное";

k = 0
i = 2
while i * i <=n:
    if n % i == 0:
        k += 1
        break
    i += 1
if k == 0:
    print("Число простое")
else:
    print("Число составное").

k := 0;
i := 2;
while i * i <= n do
begin
  if n mod i = 0 then
  begin
    k := k + 1;
    break;
  end;
  i := i + 1;
end;
if k = 0 then
  write('Число простое')
else
  write('Число составное');


 

Задача

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [1014260; 3025423], простые числа. Выведите первые 20 найденных простых чисел в порядке возрастания, слева от каждого числа выведите его номер по порядку.
 
Пример вывода первых 3 чисел
1 1014263
2 1014287
3 1014301
...

Вам необходимо вывести все числа из указанного диапазона.


 

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6411
Python195
Комментарий учителя