Как найти минимальный нетривиальный делитель - Исправление недочетов и поиск решений вместе с Examum.ru

Перейти к содержимому

Формулировка. Дано натуральное число. Найти его наименьший нетривиальный делитель или вывести само это число, если такового нет.

Решение. Задача решается аналогично предыдущей. При этом необходимо начать обычный цикл с увеличением, при котором переменная цикла i изменяется от 2 до n (такая верхняя граница нужна для того, чтобы цикл всегда заканчивался, так как когда i будет равно n, выполнится условие n mod i = 0). Весь остальной код при этом не отличается.

Код:

program SmallestDiv;
var
i, n: word;
begin
readln(n);
for i := 2 to n do begin
if n mod i = 0 then begin
writeln(i);
break
end
end
end.

Источник

Найти наибольший нетривиальный делитель натурального числа

Формулировка. Дано натуральное число. Найти его наибольший нетривиальный делитель или вывести единицу, если такового нет.

Примечание 1: делителем натурального числа a называется натуральное число b, на которое a делится без остатка. То есть выражение «b – делитель a» означает: a / b = k, причем k – натуральное число.

Примечание: нетривиальным делителем называется делитель, который отличен от 1 и от самого числа (так как на единицу и само на себя делится любое натуральное число).

Решение. Пусть ввод с клавиатуры осуществляется в переменную n. Попробуем решить задачу перебором чисел. Для этого возьмем число на единицу меньшее n и проверим, делится ли n на него. Если да, то выводим результат и выходим из цикла с помощью оператора break. Если нет, то снова уменьшаем число на 1 и продолжаем проверку. Если у числа нет нетривиальных делителей, то на каком-то шаге проверка дойдет до единицы, на которую число гарантированно поделится, после чего будет выдан соответствующий условию ответ.

Хотя, если говорить точнее, следовало бы начать проверку с числа, равного n div 2 (чтобы отбросить дробную часть при делении, если n нечетно), так как ни одно натуральное число не имеет делителей больших, чем половина это этого числа. В противном случае частное от деления должно быть натуральным числом между 1 и 2, которого просто не существует.

Данная задача также решается через for, но через другую его разновидность, и теперь счетчик будет убывать от n div 2 до 1. Для этого do заменится на downto, при позиции начального и конечного значений остаются теми же.

Алгоритм на естественном языке:

1) Ввод n;

2) Запуск цикла, при котором i изменяется от n div 2 до 1. В цикле:

Если n делится на i (то есть, остаток от деления числа n на i равен 0), то выводим i на экран и выходим из цикла с помощью break.

Код:

program GreatestDiv;
var
i, n: word;
begin
readln(n);
for i := n div 2 downto 1 do begin
if n mod i = 0 then begin
writeln(i);
break
end
end
end.

Кстати, у оператора ветвления if в цикле отсутствует else-блок. Такой условный оператор называется оператором ветвления с одной ветвью.

Задача № 14. Найти наибольший нетривиальный делитель натурального числа

Примечание 1: делителем натурального числа a называется натуральное число b, на которое a делится без остатка. То есть выражение «b – делитель a» означает: a / b = k, причем k – натуральное число.

Данная задача также решается через for, но через другую его разновидность, и теперь счетчик будет убывать от n div 2 до 1. Для этого do заменится на downto, при позиции начального и конечного значений остаются теми же.

Алгоритм на естественном языке:

1) Ввод n;

2) Запуск цикла, при котором i изменяется от n div 2 до 1. В цикле:

1. Если n делится на i (то есть, остаток от деления числа n на i равен 0), то выводим i на экран и выходим из цикла с помощью break.

Код :

1. program GreatestDiv; 2. 3. var 4. i, n: word; 5. 6. begin 7. readln(n); 8. for i := n div 2 downto 1 do begin 9. if n mod i = 0 then begin 10. writeln(i); 11. break 12. end 13. end 14. end.

Задача № 15. Найти наименьший нетривиальный делитель натурального числа

Решение. Задача решается аналогично предыдущей. При этом необходимо начать обычный цикл с увеличением, при котором переменная цикла i изменяется от 2 до n (такая верхняя граница нужна для того, чтобы цикл всегда заканчивался, так как когда i будет равно n, выполнится условие n mod i = 0). Весь остальной код при этом не отличается.

Код :

1. program SmallestDiv; 2. 3. var 4. i, n: word; 5. 6. begin 7. readln(n); 8. for i := 2 to n do begin 9. if n mod i = 0 then begin 10. writeln(i); 11. break 12. end 13. end 14. end.

Задача № 16. Подсчитать общее число делителей натурального числа

Формулировка. Дано натуральное число. Подсчитать общее количество его делителей.

Решение. Задача достаточно похожа на две предыдущие. В ней также необходимо провести перебор в цикле некоторого количества натуральных чисел на предмет обнаружения делителей n, но при этом необходимо найти не первый из них с какого-либо конца отрезка [1, n] (это отрезок, содержащий все числа от 1 до n включительно), а посчитать их. Это можно сделать с помощью счетчика count, который нужно обнулить непосредственно перед входом в цикл. Затем в условном операторе if в случае истинности условия делимости числа n (n mod i = 0) нужно увеличивать счетчик count на единицу (это удобно делать с помощью оператора inc).

Алгоритм на естественном языке:

1) Ввод n;

2) Обнуление переменной count (в силу необходимости работать с ее значением без предварительного присваивания ей какого-либо числа)

3) Запуск цикла, при котором i изменяется от 1до n. В цикле:

1. Если n делится на i (то есть, остаток от деления числа n на i равен 0), то увеличиваем значение переменной count на 1;

4) Вывод на экран значения переменной count.

Код :

1. program CountDiv; 2. 3. var 4. i, n, count: word; 5. 6. begin 7. readln(n); 8. count := 0; 9. for i := 1 to n do begin 10. if n mod i = 0 then inc(count) 11. end; 12. writeln(count) 13. end.

Задача № 17. Проверить, является ли заданное натуральное число простым

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

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

Решение. Задача отличается от предыдущей только тем, что вместо вывода на экран числа делителей, содержащегося в переменной count, необходимо выполнить проверку равенства счетчика числу 2. Если у числа найдено всего два делителя, то оно простое и нужно вывести положительный ответ, в противном случае – отрицательный ответ. А проверку через условный оператор, как мы уже знаем, можно заменить на вывод результата самого булевского выражения с помощью оператора write (writeln).

Код:

Дата добавления: 2018-10-25 ; просмотров: 1436 ; Мы поможем в написании вашей работы!

Что такое нетривиальный делитель

—>
Тип 25 № 29673

Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Например, у числа 6 есть два нетривиальных делителя: 2 и 3. Найдите все натуральные числа, принадлежащие отрезку [123456789; 223456789] и имеющие ровно три нетривиальных делителя. Для каждого найденного числа запишите в ответе его наибольший нетривиальный делитель. Ответы расположите в порядке возрастания.

Например, в диапазоне [5; 16] ровно три различных нетривиальных делителя имеет число 16, поэтому для этого диапазона вывод на экране должна содержать следующие значения:

Если решать задачу перебором — программа будет существенно неэффективна по времени. Заметим, что у каждого делителя числа имеется пара, например, пары делителей числа 16 будут выглядеть так: 1 и 16, 2 и 8, 4 и 4, всего пять различных делителей. Отсюда можно заключить, что имеет смысл перебирать возможные делители числа от единицы до корня от самого числа и, находя очередной делитель, прибавлять к переменной numDel 2. Также заметим, что поскольку число должно иметь три нетривиальных делителя, можно рассматривать только числа, квадратной корень из которых равен целому числу. Также отдельно будем учитывать квадратный корень числа, накапливая при этом в переменной numDel единицу.

Источник

0 / 0 / 0

Регистрация: 26.06.2012

Сообщений: 14

Найти и вывести на экран наибольший нетривиальный делитель числа

26.06.2012, 22:17. Показов 8042. Ответов 2

Пользователь вводит с клавиатуры натуральное число, найти и вывести на экран наибольший нетривиальный (т.е. не равный введённому числу или единице) делитель числа, либо сообщить, что число простое. Например, если пользователь ввёл 17, то на экран выводится сообщение «число простое»; если пользователь ввёл 24, то на экран выводится сообщение «наибольший нетривиальный делитель: 12».

Invader_Zim

Twilight Parasite

154 / 150 / 7

Регистрация: 21.07.2011

Сообщений: 908

26.06.2012, 22:25

Сообщение было отмечено НикНик как решение

Решение

НикНик, проверяй сначала на простоту.

C++

int a=66;
for(int i=2;i<a;i++){
    if(a%i==0)
     break;
}

rinat_w

92 / 88 / 17

Регистрация: 13.11.2011

Сообщений: 193

26.06.2012, 22:33

НикНик,

C++

#include<iostream>
using namespace std;
int main(){
    int n, d;
    cin>>n;
    int i=n/2;
    while (n%i!=0) i--;
    if (i!=1) cout<<"NND: "<<i<<endl;
    else cout<<"prime numbern";
    system("pause");
    return 0;
}

Источник

Задача № 15. Найти наименьший нетривиальный делитель
натурального числа

Формулировка. Дано натуральное число. Найти его
наименьший нетривиальный делитель или вывести само это число, если такового
нет.

Решение. Задача решается аналогично предыдущей. При
этом необходимо начать обычный цикл с увеличением, при котором переменная цикла
i изменяется от 2 до n (такая верхняя граница нужна для того, чтобы цикл
всегда заканчивался, так как когда i будет равно n, выполнится
условие n mod i
= 0). Весь остальной код при этом не отличается.

Код:

1.
program SmallestDiv;

3.
var

4.
  i, n: word;

6.
begin

7.
  readln(n);

8.
  for i := 2 to n do begin

9.
    if n mod i = 0 then begin

10.
writeln(i);

11.
break

12.
end

13.
end

14.
end.

Скачано с www.znanio.ru

Источник

2.1 Парадокс дней рождения

Теорема 2.3 Пусть . Для случайной выборки объёма из элементов, где , вероятность того, что все элементы выборки будут попарно различны, допускает следующую оценку сверху:

$p<e^{-lambda}.$

Следствие 2.1 (Парадокс дней рождения) Чтобы с вероятностью обнаружить двух людей, празднующих день рождения в один день, достаточно рассмотреть всего 23 человека.

Этот парадокс допускает следующие применения в криптографии.

2.2.1 Алгоритм Полларда для факторизации натурального числа

Пусть нам требуется факторизовать натуральное число , то есть найти любой его нетривиальный делитель. Один из простейших алгоритмов приведён ниже [1]. Алгоритм будет вычислять псевдослучайную последовательность . Вероятность того, что можно оценить по теореме 2.4. Если — минимальный делитель числа , то множество разбивается на классов, причем если x_i , x_j лежат в одном классе, то делится на . Итак, в теореме 2.4 находим $lambda = dfrac{l^2}{2q}$ , и $p<e^{-lambda}$ .

Если , а 2^r — наименьшая степень двойки, большая , то $x_{2^r}-x_{j+(2^r-i)}=0~(mod q)$ . Поэтому вместо того, чтобы сравнивать все пары x_i , x_j с произвольными i,j , имеет смысл сравнивать пары:

$begin{array}{ccc} x_2 text{ и } x_3 & x_4 text{ и } x_7 & ... \ x_4 text{ и } x_5 & x_8 text{ и } x_9 & x_{2^k} text{ и } x_{m}\ x_4 text{ и } x_6 & x_8 text{ и } x_{10} & 2^k<m<2^{k+1}. end{array}$

Для сравнения среди таких пар достаточно хранить $x_{2^k}$ и x_m , тогда как для поиска среди всех пар нужно хранить все пары.

Правда, такая хитрость требует увеличить длину последовательности. Допустим, наименьшие и , для которых , равны, соответственно, и . Тогда

$begin{array}{l} НОД(x_{l}-x_0,n)>1,\ НОД(x_{l+1}-x_1,n)>1,\ ldots\ НОД(x_{l+2^k}-x_{2^k})>1 end{array}$

Поскольку мы сравниваем $x_{2^k}$ и $x_{m}$ , где $m<2^{k+1}$ , то у нас $2^{k+1}>l+2^k$ , то есть $2^{k} > l$ . Итак, нужно выбрать наименьшее такое, что 2^k > l и вычислить не l+1 , а членов последовательности.

Взять многочлен с целыми коэффициентами и случайное число . Положить .
Вычислить $x_i=f(x_{i-1}) ~(mod n)$ .
Если — степень двойки, положить , , перейти к предыдущему шагу.
(Теперь — не степень двойки). Если , то — нетривиальный делитель числа .
Положить . Если , перейти к шагу 2.

Отметим, что при фиксированном длина вычисляемой последовательности пропорциональна sqrt{n} — верхней оценке наименьшего простого делителя . Таким образом, данный алгоритм имеет сложность, экспоненциальную по числу бит числа .

Пример 2.2 С помощью -алгоритма Полларда найти нетривиальный простой делитель числа .

На первом шаге алгоритма требуется выбрать многочлен f(x) для генерации последовательности x_i . Возьмём . Выберем длину последовательности так, чтобы найти в ней повтор с вероятностью . $qleqsqrt{2449}<50=q_0$ — оценка сверху для наименьшего простого делителя числа . Итак, $0.5< p < e^{-lambda}$ , откуда . Тогда

$l leq sqrt{2lambdacdot p_0} approx sqrt{70}approx 8,36.$

Допустим, в последовательности есть повтор. Чтобы гарантированно его найти с помощью приведённого алгоритма, нужно вычислить не меньше её членов. В самом деле, так как , то k=4 , и необходимое число членов: 25=16+9 .

Выберем x_0=10 .

Итак, нам повезло найти нетривиальный делитель 31 числа 2449. Если бы мы досчитали до $x_{25}$ и не нашли повтор, то нам лучше было бы выбрать новый x_0 (в качестве него можно взять $x_{25}$ ) и начать алгоритм сначала.

2.2.2 Алгоритм Полларда для дискретного логарифмирования

Изменим алгоритм предыдущего параграфа так, чтобы с его помощью решать задачу дискретного логарифмирования. Его идея остаётся прежней: мы будем вычислять последовательность и будем находить среди них пары x_i=x_j чисел. Зададим последовательность так, чтобы это равенство давало нам дискретный логарифм.

Найдём из условия , где — простое число.

Определим последовательности u_i , v_i , x_i следующим образом:

$u_{i+1}=left{ begin{array}{ll} u_{i}+1 ~(mod p-1),&text{если}~0leq x_i<p/3; \ 2u_{i} ~(mod p-1),&text{если}~p/3 leq x_i<2p/3; \ u_i ~(mod p-1)&text{иначе}. end{array}right.$

$v_{i+1}=left{ begin{array}{ll} v_{i} ~(mod p-1),&text{если}~0leq x_i<p/3; \ 2v_{i} ~(mod p-1),&text{если}~p/3 leq x_i<2p/3; \ v_i+1 ~(mod p-1)&text{иначе}. end{array}right.$

$x_{i+1}=b^{u_{i+1}}cdot a^{v_{i+1}}.$

Тогда если x_i=x_j , то $b^{u_{i}-u_{j}} = a^{v_{i}-v_{j}}$ , откуда

$log_a b = (u_i -u_j)^{-1} (v_i-v_j)~(mod p-1) .$

Коллизия x_i=x_j ищется тем же способом, что и в предыдущем параграфе.

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

Источник