Algorithm
to find GCD (greatest common deviser)
Primary
school GCD method
//computer gcd of m and n value by primary school method
//input: two non-negative integers and non zero and array m
& n //of n size
//output: the greates common diviser of m and n value
using System;
using
System.Collections.Generic;
using
System.Linq;
using
System.Text;
namespace sieve
{
class algo
{
int
n,j;
int[]
arr;
int[]
l;
int[]
m;
int[]
_n;
public
algo() { }
public
algo(int _m)
{
n = _m + 1;
arr = new
int[n];
l = new
int[n];
m = new
int[n];
_n = new
int[n];
}
public void sievealgo()
{
for
(int p = 2; p < n; p++)
{
arr[p] = p;
}
for
(int p = 2; p < Math.Sqrt(n)
; p++)
{
if
(arr[p] != 0)
{
j = p * p;
}
while
(j <= n-1)
{
arr[j] = 0;
j += p;
}
}
int
i = 0;
for
(int a = 0; a < n; a++)
{
if
(arr[a] != 0)
{
l[i] = arr[a];
i++;
}
}
for
(int p = 0; p < n; p++)
{
if
(l[p] != 0)
Console.WriteLine(l[p]);
}
}
public void primegcd(int _m,int nn)
{
int
valuem = _m;
int
d=0,st=0;
while
(valuem != 1 && l[st] != 0)
{
if
(valuem % l[st] == 0 )
{
m[d] = l[st];
valuem = valuem / l[st];
st = 0;
d++;
}
else
st++;
}
int
valuenn = nn;
int
dd = 0, stt = 0;
while
(valuenn != 1 && l[stt] != 0)
{
if
(valuenn % l[stt] == 0)
{
_n[dd] = l[stt];
valuenn = valuenn / l[stt];
stt = 0;
dd++;
}
else
stt++;
}
for
(int p = 0; p < n; p++)
{
if(_n[p]
!= 0 || m[p]!=0)
Console.WriteLine("m= {0}\t n= {1}",m[p],_n[p]);
}
int
gcd=1;
int
i = 0;
while(m[i]
!= 0)
{
for
(int j = 0; j < n; j++)
{
if
(_n[j] == m[i] && m[i] != 0)
{
gcd =gcd * _n[j];
_n[j] = 0;
m[i] = 0;
}
}
i++;
}
Console.WriteLine("vale m= {0}\t value
n={1}", _m, nn);
Console.WriteLine("gcd {0}", gcd);
}
}
class Program
{
static void Main(string[]
args)
{
algo
a = new algo(32);
a.sievealgo();
Console.WriteLine("seprator");
a.primegcd(150,154);
}
}
}
No comments:
Post a Comment