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 –

1. At first, check if 2 is factor of given number. So, while 2 is factor of n, add 2 in array arr and divide the number by 2.
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
3. 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 arr if 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 statement

  Suppose 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.