Пример реализации «Решета Эратосфена» и теста Миллера-Рабина

#include <FLINT.h>

#include <stdio.h>

#include <conio.h>

#include <math.h>

#define ClintToStr xclint2str_l // Переопределение функции xclint2str_l

int main(int argc, char* argv[ ])

{

CLINT a; // Обьявление объекта CLINT

// Вероятностный тест Миллера-Рабина

char *sa =new char;sa="445";

str2clint_l (a,sa,10);//Инициализация строкой

printf("a= %s",ClintToStr(a,10,0));

ULONG N=1445;

int Test= prime_l ( a, N, 1000); // тест

if(Test==1)printf(" -> Yes ");

else printf(" -> No ") ;

// Генератор простых чисел (решето Эратосфена)

ULONG M=3445;

ULONG * k= genprimes ( M);// Генератор

int m= k[0];

printf("\n Search = %d\n",m);

for(int i=1;i<=m;i++) printf(" %d ",*(k+i));

getch(); return 0

Теоретико-числовые функции Наибольший общий делитель

Наибольшим общим делителем (НОД) целых чисел а и b называ­ется положительный делитель чисел а и b, делящийся на любой другой общий делитель этих чисел. Числа а и b называются взаимно-простыми, если НОД(a,b)=1. Классический алгоритм Евклида для вычисления наибольшего общего делителя, «дедушка» всех алгоритмов [Knut], использует повторное де­ление с остатком: вычисляется вычет a mod b, затем b mod (a mod b) и так далее, пока остаток не будет равен нулю. Например: НОД(21,12) =Н0Д(21 (mod 12), 12) = НОД (9,12) = НОД(12 (mod 9), 9) = НОД (3,9) = НОД (9 (mod3),3) = НОД (0,3) = 3.

Модифицированный, т.н. бинарный алгоритм Евклида вычисления НОД(а,b) для a, b >0 реализован в виде следующей функции

Наибольший общий делитель (НОД)

Синтаксис: void gcd_l (CLINT a, CLINT b, CLINT c);

Вход: a, b (операнды)

Выход: c (наибольший общий делитель)

Таким образом, получаем представление наибольшего общего де­лителя g=НОД(a, b)=ua+vb в виде линейной комбинации чи­сел а и b с целыми коэффициентами и и v, причем u по модулю ag и v по модулю bg определены однозначно. Если же для элемента выполняется условие НОД(а, n) = 1 = и а + vп, то отсюда сразу же следует и a mod п или, что то же самое. В этом случае вычет и mod n определен однозначно.

Расширенный алгоритм Евклида вычисления линейного представ­ления НОД(а, b) = u • а + v • b для натуральных чисел a, b

Синтаксис void xgcd_l (CLINT a, CLINT b, CLINT g,CLINT u, int *sign_u, CLINT v, int *sign_v);

Вход: a , b (операнды)

Выход: g (наибольший общий делитель чисел а и b)

u, v (коэффициенты при а и b )

sign_u (знак коэффициента u)

sign_v (знак коэффициента v)

Наименьшее общее кратное

Наименьшее общее кратное (НОК) двух целых чисел a и b есть наименьшее целое число, которое делится на m и n. Обычно обозначается [a,b], а иногда НОК(a,b).

Наименьшее общее кратное двух чисел a, b равно частному от деления абсолютной величины произведения на наибольший общий делитель:

НОК(a,b) НОД(a,b) =|ab|. Это соотношением используется для вычисления НОК в следующей функции

Наименьшее общее кратное (НОК)

Синтаксис: int lcm_l (CLINT a, CLINT b, CLINT c);

Вход: a, b (операнды)

Выход: c (наименьшее общее кратное)

Возврат: E_CLINT_OK, если все в порядке E_CLINT_OFL в случае переполнения

Программная реализация нахождения НОД и НОК

#include <stdlib.h>

#include <stdio.h>

#include <string.h>

#include "d:\ FLINT.h"

#define ClintToStr xclint2str_l // Переопределение функции xclint2str_l

int main()

{

CLINT a,b,c,g,u,v;

int sign_u,sign_v;

char *s1 =new char;s1="110"; // Строка 10-х цифр

str2clint_l (a,s1,10);//Инициализация строкой

char *s2 =new char;s2="90"; // Строка 10-х цифр

str2clint_l (b,s2,10);//Инициализация строкой

printf("a=%s\n",ClintToStr(a,10,1));

printf("b=%s\n",ClintToStr(b,10,1));

// Наибольший общий делитель (НОД)

gcd_l ( a, b, c);

printf("HOD(a,b)=%s\n",ClintToStr(c,10,1));

//Наименьшее общее кратное (НОК)

int Err= lcm_l ( a, b, c);

if(Err==0) printf("HOK(a,b)=%s\n",ClintToStr(c,10,1));

/********************************************************

Расширенный алгоритм Евклида вычисления линейного представления

НОД(а, Ь) = v*g + u*b для натуральных чисел a, b

**********************************************************/

xgcd_l (a, b, g, u, &sign_u, v, &sign_v);

printf("HOD(a,b)=%s\n",ClintToStr(g,10,1));

printf("U=%s\n",ClintToStr(u,10,1));

printf("V=%s\n",ClintToStr(v,10,1));

printf("sign_U=%d\n",sign_u);

printf("sign_V=%d\n",sign_v);

return 0;

}