Алгоритм, который устанавливает – является ли число простым

@Mariasha · Регистрация: 31.08.2013

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

5. Алгоритм, который устанавливает – является ли число N
простым. Число называется простым, если оно делится нацело
без остатка только на себя и на 1.

@Forb7 · 19.02.2016, 08:17

благодарствую

@bormant · 14.12.2018, 20:28

Cyborg Drone, ФедосеевПавел,
а вот еще интересная ссылочка в тему:
https://en.wikipedia.org/wiki/Wheel_factorization

Говорят, после 2, 3, 5 можно использовать не (2, 4), а (4, 2, 4, 2, 4, 6, 2, 6).

@Cyborg Drone · 15.12.2018, 10:30

Ну, при бОльшем количестве известных простых чисел можно ещё бОльшими инкрементами идти... Но нужна будет мемоизация.
Это колесо, фактически, решето, я этот способ исключения составных чисел видел и ранее, но не в виде колеса, а в виде таблицы. Только вот насчёт уменьшения количества проверок как-то не сообразил.

@JuriiMW · 15.12.2018, 17:39

Cyborg Drone, больше уже не эффективно.

Последовательность, что привёл bormant, состоит всего из 8 элементов и содержит всего 3 составных числа в первой сотне.

А следующая последовательность начинается с 7 и содержит уже 48 элементов и, хотя оно даёт отсеять за один цикл значения уже до 221, но среди них встретится 5 составных или 3 в первой сотне.

Выигрыш не очень…
А реализация хуже ;–(

Если хотите, то вот:

[5](+2+6)
[7](+4+2+4+2+4+6+2+6)
[11](+2+4+2+4+6+2+6+4+2+4+6+6+2+6+4+2+6+4+6+ 8+4+2+4+2+4+8+6+4+6+2+4+6+2+6+6+4+2+4+6+ 2+6+4+2+4+2+10+2+10)

@bormant · 15.12.2018, 18:04

К слову, о реализации... В первом приближении:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function IsPrime(n: Longint): Boolean;
const delta: array [0..7] of Word = (4, 2, 4, 2, 4, 6, 2, 6);
var i, j, sqrtn: Word;
begin
  if (n >= 7) and ((n - 1) mod 6 = 0) or ((n + 1) mod 6 = 0) then begin
    i := 7; j := 0;
    sqrtn := Trunc(SqRt(n));
    IsPrime := False;
    while i <= sqrtn do begin
      if n mod i = 0 then Exit;
      Inc(i, delta[j]);
      Inc(j); if j = 8 then j := 0;
    end;
    IsPrime := True;
  end else
    IsPrime := (n = 2) or (n = 3) or (n = 5);
end;

Новые блоги и статьи Все статьи Все блоги /
Часы электронные Uhbif79 12.08.2026 Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .	Часы с будильником на основе класса QLCDNumber Uhbif79 12.08.2026 Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .	Установка MinGW GCC 16.2 и CMake 8Observer8 10.08.2026 VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия	Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо anaschu 10.08.2026 Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .
Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .	Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .

@Mariasha 0 / 0 / 0 Регистрация: 31.08.2013 Сообщений: 26

	Алгоритм, который устанавливает – является ли число простым 01.04.2015, 14:27. Показов 28069. Ответов 24 Метки нет (Все метки) 5. Алгоритм, который устанавливает – является ли число N простым. Число называется простым, если оно делится нацело без остатка только на себя и на 1. 0

@Forb7 -4 / 0 / 0 Регистрация: 18.02.2016 Сообщений: 26
	19.02.2016, 08:17
	благодарствую 0

@bormant Модератор 7818 / 4637 / 2837 Регистрация: 22.11.2013 Сообщений: 13,159 Записей в блоге: 1
	14.12.2018, 20:28
	Cyborg Drone, ФедосеевПавел, а вот еще интересная ссылочка в тему: https://en.wikipedia.org/wiki/Wheel_factorization Говорят, после 2, 3, 5 можно использовать не (2, 4), а (4, 2, 4, 2, 4, 6, 2, 6). 2

@Cyborg Drone Модератор 10476 / 5771 / 3411 Регистрация: 17.08.2012 Сообщений: 17,528
	15.12.2018, 10:30
	Ну, при бОльшем количестве известных простых чисел можно ещё бОльшими инкрементами идти... Но нужна будет мемоизация. Это колесо, фактически, решето, я этот способ исключения составных чисел видел и ранее, но не в виде колеса, а в виде таблицы. Только вот насчёт уменьшения количества проверок как-то не сообразил. 0

@JuriiMW 5096 / 2662 / 2355 Регистрация: 10.12.2014 Сообщений: 10,060
	15.12.2018, 17:39
	Cyborg Drone, больше уже не эффективно. Последовательность, что привёл bormant, состоит всего из 8 элементов и содержит всего 3 составных числа в первой сотне. А следующая последовательность начинается с 7 и содержит уже 48 элементов и, хотя оно даёт отсеять за один цикл значения уже до 221, но среди них встретится 5 составных или 3 в первой сотне. Выигрыш не очень… А реализация хуже ;–( Если хотите, то вот: [5](+2+6) [7](+4+2+4+2+4+6+2+6) [11](+2+4+2+4+6+2+6+4+2+4+6+6+2+6+4+2+6+4+6+ 8+4+2+4+2+4+8+6+4+6+2+4+6+2+6+6+4+2+4+6+ 2+6+4+2+4+2+10+2+10) 0