Определить, есть ли в заданном диапазоне чисел простые числа-близнецы

@milanwins · Регистрация: 02.11.2016

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

Помогите составить программу
Дано натуральное число n. Выяснить, имеются ли среди чисел n, n+1, …, 2n близнецы, т. е. простые числа, разность между которыми равна двум. Определить процедуру, позволяющую распознавать простые числа.

@Cyborg Drone · 06.11.2016, 23:42

Процедуру? С функцией было бы проще. А ещё проще было бы с функцией, определяющей не простоту числа, а факт того, что два числа являются простыми числами-близнецами. В последнем случае никакие подпрограммы, вообще говоря, не требуются, так как их вызов будет происходить с одними и теми же фактическими параметрами, хотя, в принципе, функция всё же может быть применена с целью декомпозиции алгоритма. Ну да ладно.

Начнём с теории. Любое простое число n, большее 3, может быть представлено либо в виде 6k-1, либо в виде 6k+1, где k - некоторое натуральное число. Абстрагируясь от k, можно сказать, что, если число n простое, то либо n-1, либо n+1 делится нацело на 6. Действительно, если, например, 6k-1=n, то k=(n+1) div 6, а, так как k по определению натуральное, то n+1 делится на 6 нацело. Для 6k+1 та же бадяга. Но не стоит слишком обольщаться, обратное не верно, если выполняются указанные условия насчёт деления без остатка, вовсе не обязательно, что число n будет простым. Например, 25-1 делится нацело на 6, но 25 - составное число.

Что интересно, если два числа являются парой простых чисел-близнецов (кроме пары 3, 5), то эта пара может быть опять же представлена в виде 6k±1, где k - некоторое натуральное число. То есть, можно смело проверять не все числа, а только числа, кратные 6 (пусть это будут числа s = 6, 12, 18 и т. д.) и если числа s-1 и s+1 (оба) простые, то они близнецы.

Процедура определения простоты числа переделана из функции, взятой отсюда: Алгоритм, который устанавливает – является ли число простым (пост #19). Так как используются только числа вида 6k±1, лишние проверки на делимость на 6 из процедуры убраны. Если эта процедура представляется Вам сложной, найдите на этом форуме одну из +100500 функций определения простоты числа, которая будет видеться Вам не столь запутанной, и переделайте её в процедуру. Вот, правда, что-то не припомню, чтобы видел именно процедуру определения простоты числа, поэтому подозреваю, что найти таковую вряд ли удастся.

Программа по заданию, на основе вышеизложенного:

Pascal

procedure IsPrime(n: longint; var res: boolean);
var i, sqrtn, delta: word;
begin
  if n >= 5
    then begin
      i := 5;
      delta := 2;
      sqrtn := trunc(sqrt(n));
      res := false;
      while i <= sqrtn do
        begin
          if n mod i = 0 then exit;
          inc(i, delta);
          delta := delta xor 6 {смена шага, то 2, то 4}
        end;
      res := true;
    end
    else res := (n = 2) or (n = 3)
end;
 
var n, s, e: longint;
    f, g: boolean;
begin
  repeat //ввод n с проверкой
    write('n > 0;  n = ');
    readln(n)
  until n > 0;
  g := n = 3; //определяем, есть ли пара (3, 5)
  if not g and (n > 3) //если пары (3, 5) нет, и интервал не (1, 2) или (2, 4), проверяем интервал n..2n
    then begin
      e := 2 * n; //верхняя граница интервала
      s := n + 6 - n mod 6; //уточняем нижнюю границу интервала - находим ближайшее число, кратное 6, большее n
      dec(e); //уточняем верхнюю границу интервала - находим ближайшее число, кратное 6, меньшее 2n
      e := e - e mod 6;
      while s <= e do //цикл по всем числам интервала n..2n, кратным 6
        begin
          IsPrime(s - 1, f); //проверяем на простоту s-1
          IsPrime(s + 1, g); //проверяем на простоту s+1
          g := f and g; //определяем факт того, что оба числа простые одновременно
          if g then break; //если оба простые, то досрочно выходим из цикла
          inc(s, 6) //если досрочно из цикла не вышли, берём следующее число, кратное 6
        end
    end;
  write('На интервале [', n, '..', 2 * n, '] ');
  if g //если близнецы найдены
    then write('есть простые числа-близнецы') //то печатаем, что они есть
    else write('нет простых чисел-близнецов'); //иначе печатаем, что их нет
  readln //любуемся результатом
end.

Да, вот ещё что... На самом деле, для подходящих натуральных чисел из диапазона типа longint, по факту для n в диапазоне [1..1073741823], интервалов вида [n..2n], не содержащих близнецов, всего три, при n, равном 1, 2, или 6. При любом другом n близнецы есть. Так что, не удивляйтесь, что программа практически всегда находит близнецов, это так и должно быть.

@milanwins 0 / 0 / 0 Регистрация: 02.11.2016 Сообщений: 2
		1
	Определить, есть ли в заданном диапазоне чисел простые числа-близнецы 02.11.2016, 23:08. Показов 4207. Ответов 1 Метки нет (Все метки) Помогите составить программу Дано натуральное число n. Выяснить, имеются ли среди чисел n, n+1, …, 2n близнецы, т. е. простые числа, разность между которыми равна двум. Определить процедуру, позволяющую распознавать простые числа. 0

	06.11.2016, 23:42

Определить, есть ли в заданном диапазоне чисел простые числа-близнецы

Решение