Простые понятия и алгоритмы теории чисел(для 1го курса).

Алгоритм Евклида и алгоритм нахождения НОК(базовые варианты).

НОД - это наибольшее целое число, на которое делятся одновременно a и b.

По определению, если одно из чисел равно 0, то ответом будет второе.

Описание алгоритма:

Имеются два числа, необходимо найти для них наибольший общий делитель

По алгоритму Евклида имеем:

Если с(остаток от деления a на b) не равен 0, то возьмем остаток от деления

большего из a, b, иначе ответом на задачу будет число из пары a,b отличное от 0.

Реализация алгоритма на языке С++, оформленная в виде функции:

int gcd(int a, int b)

{

while(a&&b) // главное условие

if(a>b) // ищем большее и берем остаток от деления в него, меньшее остается без изменений

a %= b;

else

b %= a;

return b+a; // одно из них 0, другое ответ на задачу

}

НОК чисел и алгоритм его нахождения.

Наименьшее общее кратное двух чисел a,b – это такое минимальное число с, что оно делится одновременно на одно и на второе. Формулу его нахождения можно выразить через НОД, НОК = a*b/НОК(a,b).

int lcm(int a, int b)

{

return a/gcd(a,b)*b;

}

Понятие простого числа. Проверка числа на простоту. Нахождение всех простых чисел на заданном промежутке.

Определение. Простое число - это число, делителями которого являются только 1 и оно само, то есть, не существует такого числа b( b !=1, b!=a), что остаток от деления a на b равен 0.

Любое составное число можно выразить как произведение простых чисел, меньших, чем заданное. Следовательно, для проверки числа на простоту, достаточно проверить его остаток от деления на простые числа, меньшие, чем оно само. Если делители на заданном промежутке не найдены, то число простое, в противном случае – составное. Стоит заметить, что для нахождения делителей достаточно осуществить их поиск от 2(наименьшее простое число) до корня из этого числа. Заметим, что sqrt(a) * sqrt(a) = a, тогда, очевидно, целое число можно представить в виде произведения двух числе b,c, при этом с ростом b, уменьшается c. Очевидно, что при b=c: b*c = a тогда и только тогда, когда b = sqrt(a), c = sqrt(a). Использую то свойство, что мы уже перебрали все числа из диапазона от 2 до sqrt(a), становятся видно, что рассматриваемые делители мы уже перебрали и рассматриваем их в обратном порядке (при этом второй делитель возрастает, первый убывает).

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

Реализация алгоритма поиска, без предпосчитанных простых (просто будем искать среди нечетных, меньших, чем корень из числа).

int itsprime(int a)

{

if(a<2 || a%2==0)

return false;

for(int i = 3; i*i <= a; i+=2)

if(!(a%i))

return false;

return true;

}

Нахождение всех простых чисел в заданном диапазоне с использованием «решета Эратосфена».

Зная, что любое простое число есть произведение составных, используем следующий алгоритм:

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

Описание реализации функции, вычисляющей простые числа: программа принимает целое число n – верхняя граница диапазона и указатель на целое число, по его адресу мы поместим значение, соответствующее количеству простых чисел. В самой функции, сначала следует непосредственная реализация описанного алгоритма, затем, подсчет количества простых чисел и процесс их размещения в массиве, который содержит только простые числа. Функция возвращает указатель на начало этого массива.

int* primes(int n,int *size)

{

int* tmp = new int[n+1];

for(int i = 0; i <= n; ++i)

tmp[i] = true;

for(int i = 2; i*i <= n; ++i)

if(tmp[i] && (long long)i*i<=n)

for(int j = i; j*i <= n; j++)

tmp[j*i] = false;

int anssum = 0;

for(int i = 2; i <= n; ++i)

if(tmp[i])

anssum++;

int *ans = new int[anssum];

int curk = 0;

for(int i = 2; i <= n; ++i)

if(tmp[i])

ans[curk++] = i;

*size = anssum;

return ans;

}