Write a Kotlin program to find all prime factors of a given number n. For example,

Given n = 10

**Output**

2 5

Given n = 20

2 2 5

## Program to find prime factors in Kotlin

We are going to write a function that returns an array which contains all the prime factors of a given number.

**Pseudo Algorithm**

Below are the steps to find all the prime factors of given number n –

- At first, check if 2 is factor of given number. So, while 2 is factor of n, add 2 in array
arrand divide the number by 2.- Since we have divided the number by 2 till is divisible by 2 in step 1, n must be odd after completing step 1. Now, run a loop from 3 to square root of n. While i divides n, add i to array
arr. Then, divides n by i. After i fails to divide n, increment i by 2. Then, continue loop- If n is prime number and greater than 2, it won’t become 1 by above two steps. So, you need to add that number in array
arrif it greater than 2.

Sourcecode –

fun main() { val scanner = Scanner(System.`in`) println("Enter a number") val n = scanner.nextInt() if (n <= 1) { println("No Prime Factor") } else { val factors = primeFactors(n) println("Prime Factors of $n") for (number in factors) { print("$number ") } } } private fun primeFactors(number: Int): ArrayList<Int> { // Array that contains all the prime factors of given number. val arr: ArrayList<Int> = arrayListOf() var n = number // At first check for divisibility by 2. add it in arr till it is divisible while (n % 2 == 0) { arr.add(2) n /= 2 } val squareRoot = sqrt(n.toDouble()).toInt() // Run loop from 3 to square root of n. Check for divisibility by i. Add i in arr till it is divisible by i. for (i in 3..squareRoot step 2) { while (n % i == 0) { arr.add(i) n /= i } } // If n is a prime number greater than 2. if (n > 2) { arr.add(n) } return arr }

Enter a number 100 Prime Factors of 100 2 2 5 5

###### Explanation

Here, we have created an object of Scanner. Scanner takes an argument which says where to take input from.

**System.`in`** means take input from standard input – Keyboard.

**read.nextIn()** means read anything entered by user before space or line break from standard input – Keyboard.

Input read by scanner is then stored in variable **n**

We have defined a function **primeFactors()** that returns array containing all the prime factors of given number **n**.

Let’s assume we have passed 10 in primeFactors function.

So, an array arr will be defined.

Now, first we check for divisibility by 2. Add 2 into array arr till n is divisible by 2.

So, for n = 10,

(n % 2 == 0) is true.

Add 2 to array **arr**

Divide the array by 2.

Now, n = 5.

(n % 2 == 0) is false.

So, while loop is exited.

Now, we find square root of 5.

That is approx 2 (sqrt(n.toDouble()).toInt() returns 2)

Now, Check if we can run for loop. Since for loop runs from 3 to square root of n (i.e. 2 in this case). We can not run for loop.

After for loop, n = 5.

Since n (=5) > 2. If condition is satisfied. So, add 5 in array arr.

So, we have 2 and 5 in array **arr**.

Return this array to calling function.

## How does this algorithm work?

Note that there are 3 steps in this algorithm.

- 1. We check if n is divisible by 2 or not. If yes, 2 is factor of n. Now, we continuously divide n by 2 and till it is not divisible. Each time we are 2 as factor of n.
- 2. After step 1, n must be odd. Now, we run a loop till square root of n. we check if n is divisible by any number from 3 to square root of n.

You might by wondering why till square root of n? why not n itself?

Answer is –Each composite number has at-least one prime factor less than or equal to square root of itself.

Proof of above statementSuppose a and b are two prime factors of n such that a * b = n.

Now, if both a and b are greater than n, then, a * b > sqrt(n) * sqrt(n)

So, a * b > n .

That contradicts our statement.

So,

At-least one factor is less than sqrt(n).Thus, we need to check till square root of n only.

Also, we increment the value of i by 2. This is because we won’t have even prime factor in step 2. We have already check of even prime factor in step 1.

So, There must be a gap by at-least 2 between two prime factors in step 2.Step 1 and 2 takes care of composite numbers.

- 3. After step 2, we get either 1 or prime number greater than 2. So, we just add the value in resultant array
arr

Thus, we went through Kotlin Program to find all the prime factors of given number.