# Prime factors of a number

### Description

A **prime number** is a number grater than 1 that can’t be divided by any number except itself and 1. **Prime factors **of a number is product of a prime numbers only.

A **prime number **is it’s own prime factor and can’t be spread.

Example: 2, 3, 5, 7, 11

**Complex numbers **have at least 2 prime factors.

Example:

10 = 2 ⋅ 5

12 = 2 ⋅ 2 ⋅ 3

100 = 2 ⋅ 2 ⋅ 5 ⋅ 5

7546 = 2 ⋅ 7 ⋅ 7 ⋅ 7 ⋅ 11

In order to make it easier to understand we can divide **n **by prime numbers. We start from the lowest number possible. Divide **n **as long as it comes down to 1:

10 : 2 = 5

5 : 5 = 1

12 : 2 = 6

6 : 2 = 33 : 3 = 1

100 : 2 = 50

50 : 2 = 25

25 : 5 = 5

5 : 5 = 1

7546 : 2 = 3773

3773 : 7 = 539

539 : 7 = 77

77 : 7 = 11

11 : 11 = 1

### Input data

*n *greater than 1.

### Output data

Prime factors of n.

### C++ code

#### Easier to understand

1 2 3 4 5 6 7 8 9 10 11 12 13 | string primeFactors(int n){ // you could also return an array of prime numbers if you need to work with them later int k = 2; // k is the lowest prime number ostringstream oss; // to append int to string while(n>1){ // execute as long as n is greater than 1 while(n%k==0){ // as long as n can be devided by k without a reminder oss << k << " "; n /= k; // divide n by k } ++k; // when the inner loop ends it's work we increment k to get next prime number } return oss.str(); } |

#### Optimized

We can optimize this code by searching prime numbers to √n.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | string primeFactors(int n){ // you could also return an array of prime numbers if you need to work with them later int k = 2; // k is the lowest prime number int sqrtn = sqrt(n); ostringstream oss; // to append int to string // cout << sqrtn << endl; while(n>1 && k <= sqrtn){ // execute as long as n is greater than 1 and k is smaller or equal to sqrt(n) while(n%k==0){ // as long as n can be devided by k without a reminder oss << k << " "; n /= k; // divide n by k } ++k; // when the inner loop ends it's work we increment k to get next prime number } if(n > 1) oss << n; return oss.str(); } |