# Algorithm and Flowchart to find the prime factors of a number

[10218 views]

### What are prime numbers?

A number is called a prime number when it has only two factors, that is, when the factors of the number are 1 and the number itself. Example: 2, 5, 11,17, 19, etc.

### What are prime factors?

The prime factors of a number are the group of prime numbers that when multiplied by each other gives the original number as the product. We can find out the prime factors of a number with the help of the prime factorization method.

For example: Prime factors of 6 are 2 and 3.
2 * 3 = 6

Prime factors of 15 are 3 and 5.
3 * 5 = 15

Now let’s take a look at the algorithm and flowchart to find out all the prime factors of a given number, with the help of an algorithm and flowchart, for better understanding.

## Algorithm to find prime factors of a number:

To avoid repetition, we have used the concept of functions. Here, we use a function to check whether a number is prime or not. We can call this function any number of times we want in the program.

#### CheckPrime(num):

Assumption: For this algorithm, we assume that the function takes a number ‘num’, which is to be checked, and returns true if the number is prime, otherwise, returns false.

Step 1: Start Step 2: Initialize the number of factors of num, f = 0 Step 3. Initialize i = 1 Step 4. Repeat until i<=num: 4.1: If num % i == 0: 4.2: Increment f by 1 4.3: Increment i by 1 Step 5: If f = 2, then: 5.1: Return True Step 6: Else: 6.1 Return False Step 7. Stop

### Algorithm to find the prime factors of a number ‘n’:

Step 1: Start Step 2: Read the number from the user, say n Step 3: Initialize loop variable i = 2 Step 4: Repeat While i <= n/2: 4.1: If n % i == 0, then: 4.1.a: If CheckPrime(i) == true, then: Display i 4.2: Increment i by 1 Step 6: Stop

## Explanation:

In this problem, we display all the prime factors of a given number. The main logic behind this is to check whether a number is divisible by the given number, if yes, then to check whether that number is prime or not. To do the prime number checking, we have written a separate function. This will save time as well as space. This function will return true if the number is prime, else return false.

To do the prime number checking, we must find out the number of factors of the number. Let us say the number is ‘num’. We first initialize the number of factors, ‘f’ as 0. Now, we start a loop from 1 to num, where the loop variable is ‘i’. If num% i=0, f is incremented by 1. In this line we are checking whether the number is divisible by ‘i’ or not. If yes, f is incremented. If the number of factors is equal to 2, the function returns 0, else it returns false.

Now, coming to the main algorithm, we start off by taking the number as user input and store it in a variable, say ‘n’. Then we initialize the loop variable ‘i’ as 2, as all numbers are divisible by 1, we start the loop by 2. We start a loop which runs until i is less than n/2. The reason behind doing so is that a factor of a number will never be greater than its half. In each iteration of this loop, we check whether n is divisible by i or not. If it is divisible by i, then we check whether i is a prime number or not, by calling the function CheckPrime(). If the function returns true, then i is a prime factor of n. We display i and the loop continues. Once the loop completes its execution, all the prime factors of n are displayed.

Note: Here ‘%’ is the modulus operator which returns the remainder value after division.