Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Простые и составные числа
Простые числа. Натуральные числа имеющие ровно два делителя (единицу и само это число) называются простыми .
Составные числа. Все числа кроме простых и единицы называются составными.
Составное число всегда можно разложить на два множителя отличных от 1.
Задача. Найти все натуральные p такие, что p, p+2, p+4 — простые.
Ответ: 3.
Решение. Пусть есть другое решение. Тогда ни одно из чисел p, p+2, p+4 не делится на 3. Но если p+4 не делится на 3, то и p+1 не делится на 3. Откуда получаем, что p, p+1 и p+2 не делятся на 3, чего быть не может.
Количество простых чисел. Простых чисел бесконечно много.
Доказательство. Предположим, что простых чисел конечное число:
2,3,5,7,11,…,p,
где p — самое большое простое число.
Составим число n:
n=2⋅3⋅5⋅7⋅11⋅…⋅p+1.
Это чисто не делится на 2, так как оно отличается на 1 от числа делящегося на 2. Так же оно те делится на 3, на 5, … на p. Значит число n не делится ни на одно простое число, что противоречит основной теореме алгебры. Полученное противоречие показывает, что наше предположение неверно и простых чисел бесконечно много.}
Решето Эратосфена. Для того, чтобы найти все простые числа не превосходящие некоторого натурального n можно воспользоваться следующим алгоритмом. Выписать подряд все целые числа от двух до n. Обвести двойку, и вычеркнуть все остальные числа делящиеся на 2 (4, 6, 8, … ). Затем, обвести первое не вычеркнутое число, и вычеркнуть все остальные числа делящиеся на него. И продолжить это процедуру пока не достигнется конец списка. Теперь все не вычеркнутые числа в списке — простые.
Алгоритм проверки числа на простоту. Для того чтобы проверить является ли число простым необязательно проверять, что оно не делится ни на одно число меньшее его. Достаточно проверить, что число не делится ни на одно из простых чисел, квадрат которых не превосходит рассматриваемое число.
Наибольший общий делитель и наименьшее общее кратное
Наибольший общий делитель. Общим делителем натуральных чисел a и b называется число, на которое делятся оба числа a и b. Наибольший общий делитель обозначается НОД(a;b).
Для нахождения НОД(a;b) нужно разложить числа a и b на простые множители, и вычислить произведение общих простых множителей в наименьших степенях, с которыми эти множители входят в разложение a и b.
Наименьшее общее кратное. Общим кратным двух натуральных чисел a и b называется число, которое делится и на a и на b. Наименьшее общее кратное обозначается НОК(a;b).
Для нахождения НОК(a;b) нужно разложить числа a и b на простые множители, и вычислить произведение всех простых множителей, входящих хотя бы в одно из разложений, в наибольших из степеней, с которыми эти множители входят в разложение a и b.
Связь между НОД и НОК. Для любых двух натуральных чисел a, b верно следующее равенство
НОД(a;b)⋅НОК(a;b)=ab.
Взаимно простые числа. Натуральные числа a и b называются взаимно простыми, если НОД(a;b)=1.
Алгоритм Евклида. Для любых двух натуральных чисел a>b верно следующее равенство
НОД(a;b)=НОД(a–b;b).
На этом утверждении основан другой способ отыскания наибольшего общего делителя двух чисел. Он называется алгоритм Евклида и заключается в следующем. Для нахождения НОД(a;b) нужно заменить большее из чисел на остаток от деления его на меньшее, и для полученной пары повторять эту процедуру, пока одно из чисел не станет равно нулю. Тогда второе число будет равно наибольшему общему делителю исходных чисел.
Например,
НОД(175;90)=НОД(85;90)=НОД(85;5)=НОД(0;5)=5.