Sunday 13 October 2013

chinese remainder theorem in c


Chinese_remainder_theorem code in C

#include <stdio.h>
main() {
int a[10],m[10],M[10],y[10];
int ml=1,n,i,j,x=0;
printf("\nEnter value of a and m as follows : \n");
printf("x mod m1=a1 mod m1\n"); printf("x mod m2=a2 mod m2\n");
printf("what is the value of n less than 10 : ");
printf("\t.\n\t.\n\t.\n\t.\n\t.\n"); printf("x mod mn=an mod mn\n"); scanf("%d",&n);
for(i=1;i<=n;i++)
//enter m1,m2,m3,m4...........mn printf("\nEnter m1,m2,m3,m4,............,mn\n"); { printf("m %d : ",i);
for(i=1;i<=n;i++)
scanf("%d",&m[i]); } //enter a1,a2,a3,a4,...........an printf("\nEnter a1,a2,a3,a4,............,an\n"); {
//compute M1,M2,M3,M4...........Mn
printf("a %d : ",i); scanf("%d",&a[i]); } //compute M ? for(i=1;i<=n;i++) { ml=ml*m[i]; } for(i=1;i<=n;i++) {
if((y[i]*j)%m[i]==1)
M[i]=ml/m[i]; } //compute y1,y2,y3,y4...........yn for(i=1;i<=n;i++) { y[i]=M[i]%m[i]; j=1; while(1) //find MI { break;
printf("\nFinal value of x : %d ans",x);
else j++; } y[i]=j; } for(i=1;i<=n;i++) { x=x+(a[i]*y[i]*M[i])%ml; } x=x%ml; //final x is here printf("\nThank u \n"); return 0;
}
Compiled By :gcc compiler in ubuntu LINUX
copy the code and give name crt.c and follow :

:gcc -o a crt.c    (compile the code).
:./a               (run the program).

No comments:

Post a Comment