Before coding the program let us first have an understanding of what HCF is and a brief information about it.

### FACTOR

**A** **factor** of a given number is every number that **divides exactly **into that number**.**

### Example

Write down all factors of 10.

10 = 2 x 5, so numbers 2 and 5 are factors of 10.

Also 10 = 10 x 1, so 10 and 1 are factors of 10.

The factors of 10 are 1, 2, 5, 10.

**NOTE**: Number **1** and the **number itself** are always factors of any number.

**COMMON FACTORS**

When two (or more) numbers have **the same factor**, that factor is called a **common factor**.

### Example

Find all the common factors of 12 and 18.

Factors of 12 are **1**, **2**, **3**, 4, **6**, 12.

Factors of 18 are **1**, **2**, **3**, **6**, 18.

The common factors of 12 and 18 are 1, 2, 3 and 6.

In number theory, the **prime factors** of a positive integer are the prime numbers that divide that integer exactly. The prime factorization of a positive integer is a list of the integer’s prime factors, together with their multiplicities; the process of determining these factors is called integer factorization. The fundamental theorem of arithmetic says that every positive integer has a single unique prime factorization.

To shorten prime factorizations, factors are often expressed in powers (multiplicities). For example,

### HIGHEST COMMON FACTOR (H.C.F).

The **Highest Common Factor (H.C.F)** of two (or more) numbers is the largest number that divides evenly into both numbers.

In other words the H.C.F is the largest of all the common factors.

The common factors or of 12 and 18 are 1, 2, 3 and 6.

The largest common factor is 6, so this is the H.C.F. of 12 and 18.

It is very easy **to** **find a H.C.F. of small numbers**, like 6 and 9 (it is 3) or 8 and 4 (it is 4).

The best way is to keep finding the factors of the smaller number, starting from the largest factor. The first factor of the smaller number that is also a factor of the larger number is a H.C.F.

**The H.C.F is useful when simplifying fractions.**

Program on HCF

Programs 1 – Common Factor Method

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
import java.util.*; public class HCF { public static void main() { Scanner sc = new Scanner(System.in); int a, b, hcf=1, i; System.out.println("Enter the first number: "); a = sc.nextInt(); System.out.println("Enter the second number: "); b = sc.nextInt(); for(i=1;i<=a;i++) { if(a%i==0&&b%i==0) hcf = i; } System.out.println("HCF: "+hcf); } } |

Program 2 – Long Division Method

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
import java.util.*; public class While_hcf { public static void main() { Scanner sc = new Scanner(System.in); int m, n, c1, c2, tmp; System.out.println("Enter the two numbers:"); m = sc.nextInt(); n = sc.nextInt(); c1=m; c2=n; while(m%n!=0) { tmp = m%n; m=n; n=tmp; } System.out.println("HCF: "+n); System.out.println("LCM: "+(c1*c2/n)); } } |

Program 3 – By Prime Factorisation Method

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
import java.io.*; public class HCF_primefactors { public static void main()throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); System.out.println("Enter two numbers:"); int a=Integer.parseInt(br.readLine()); int b=Integer.parseInt(br.readLine()); int hcf=1; for(int i=2;a!=1&&b!=1;/*Increment only when factor is absent*/) { if(a%i==0&&b%i==0) { hcf=hcf*i; a=a/i; b=b/i; } else if(a%i==0) a=a/i; else if(b%i==0) b=b/i; else i++; } System.out.println("HCF="+hcf); } } |

## Leave a Reply