YoungProgrammer

Back to Problem list

Problem 14: Given an integer, write a program to factorize this number. Example
20 = 2 X 2 X 5
30 = 2 X 3 X 5

Solution:

#include<stdio.h> #include<string.h> int main() { int pos_1, pos_2; char ch; char input[100]; gets(input); // reading the String pos_1 = 0; // first position pos_2 = strlen(input) - 1; // last position while(pos_1 < pos_2) { ch = input[pos_1]; input[pos_1] = input[pos_2]; input[pos_2] = ch; pos_1++; pos_2--; } printf("%s\n",input); return 0; }

Analysis:
let n = 100, first we try with 2,
n % 2 == 0, fact[] = {2}, total = 1, n/= i, n = n/2, n = 50
50% 2 == 0, fact[] = {2,2} total = 2, n = n/2, n = 50/2, n = 25
Next, 25 % 2 != 0, similar case for 3 and 4, so next i = 5
25%5 == 0, fact[] = {2,2,5} total = 3, n = n/5, n = 25/5 = 5
5%5 == 0, fact[] = {2,2,5,5} total = 4, n = n/5 = n = 5/5 = 1
Next, n%5 != 0 , so exit from while loop,
Now, have a close look in the for loop, given condition: i*i <= n
but i = 5 and i*i > n, so break from for loop
Finally print the fact array with proper format.

Two questions to think:
1. why i*i <= n in the for loop
2. why this condition: if(n > 1) fact[total++] = n

For second case, try n = 27 and for the first case, think yourself.

Back to Problem list