Category Archives: Number Theory

Algorithm: Euler’s GCD


code:

more optimized:

 

Recursive:

 

http://www.progkriya.org/gyan/basic-number-theory.html#section3

Algo: Prime factorization of a number

code:

I/O:

 

Prime Number: Trial division | Prime check upto N in C

code:

Help can be find:
http://www.studystreet.com/c-program-print-prime-numbers/
http://www.codingalpha.com/prime-number-c-program/
https://en.wikipedia.org/wiki/Primality_test

Prime Finding: Sieve of Erastosthenes

I have watched the videos from mycodeschool and implemented it:
code:

Video:

LCM – Least Common Multiple

Multiple of 3 is
3×1=3
3×2=6
3×3=9
3×4=12
3×5=15
3×6=18
3×7=21
3×8=24
3×9=27
3×10=30

Multiple of 4 is
4×1=4
4×2=8
4×3=12
4×4=16
4×5=20
4×6=24
4×7=28
4×8=32
4×9=36
4×10=40

Here in 3 and 4 mutilples common is 12
and it is only one value and so it is the lowest also then but if there were some more values than result could be something changed.

So here LCM=12
Here I implemented the code
applied this formula
lcm(a,b)=a*b/gcd(a,b);

code goes here :

 

GCD Greatest Common Divisor(Factor)/Highest Common Factor

এখানে লজিকটা হচ্ছে…Here the logic is:
For 12:
1×12=12
2×6=12
3×4=12
So factor of 12=1,2,3,4,6,12
(We don’t need the negative values here)

For 30:
1×30=30
2×15=30
3×10=30
5×6=30
So factor of 30=1,2,3,5,6,10,15,30

Now which is the common factor among 12 and 30
So factor of 12=1,2,3,4,6,12
So factor of 30=1,2,3,5,6,10,15,30

common factor=1,2,3,6
Largest common factor here=6

So now if we divide 12/6 then we get 2
and for 30/6 we get 5

that is all divided perfectly so the logic should be like this

1.Find all the factors of each number
2. Circle the common factors
3. Choose the greatest of those
4. Divide the existing number with greatest common factor thern also get a perfect divide

Here is my code:

gcd

Here is a link that described many thinks about this clearly: http://www.mathsisfun.com/greatest-common-factor.html

 

Another method can also apply here:
link for understanding the modarithmetic euclidean algorithmhttps://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm

Code: