Friday, May 09, 2014

Prime Factors of a Number - C Program

Problem Question


A positive integer is entered through the keyboard. Write a function to obtain the prime factors of this number.

Explanation of Problem


Our program shall accept an integer from the user and print on screen the prime factors of that number. For example, prime factors of 24 are 2, 2, 2 and 3, whereas prime factors of 35 are 5 and 7.

Code


#include <stdio.h>

/**@Title: PrimeFactors2.c*
*@Language: ANSI C*
*@Compiler: GNU GCC*
*@IDE: Code::Blocks 13.12*
*@Author: Toxifier*
*@URL: http://letsplaycoding.blogspot.com/*
*@Date: 09-05-2014*
*@Update: Updated version of the 05/05/2014 program called PrimFactors.c*
*/

int main()
{
  int number, i, primeCheck, j, flag = 1;
  printf("\n\nEnter a number: ");
  scanf("%d", &number);
  primeCheck = (number / 2) + 1;
  printf("%d = ", number);
  for ( i = 2; i < number; i++ )
  {
    if ((number % i))
    {
      flag = 1;
    }
    else
    {
      flag = 0;
      break;
    }
  }
  if (flag == 1)
    printf("1 X %d", number);
  else
  {
    for ( i = 2; i <= primeCheck; i++ )
    {
      while ( !(number % i) || (number == i) )
      {
        printf("%d ", i);
        number /= i;
        if ( number > 1 )
          printf("X ");
      }
    }
  }
  printf("\n\n");
  system("pause");
  return 0;
}

Explanation of Code


#include <stdio.h> -> This is the step which occurs before compilation starts. The compiler calls the C Preprocessor to include the STDIO(Standard Input Output) header file into the program, thus letting the use of the standard input/output functions like printf() and scanf() which come from STDIO.H

int main() -> The entry point of the program where the execution starts. This function has to be named main. As per the ANSI specification, the return type has to be int. If you use the traditional C, you may use void as the return type. Since the return type is specified as int in my program, I have to use a return statement at the end of my code. So I use return 0 since zero returned from a function, by convention, implies a correct execution of the program. The return values are used to debug the program.

printf() -> This is a standard output function used to print something on the screen. We have to pass a string to this function which will be displayed on user's terminal.

scanf() -> This is the scanf() function which waits for the user to enter certain value using his/her keyboard. We store the user input at the location in memory which is pointed to by the variable whose address is passed to this function.

int number, i, primeCheck, j, flag = 1; -> The variable 'number' is used to get the user input. The variable 'i' & 'j' are the loop counters. The variable 'primeCheck' is used as the upper limit for the loop that checks if the number entered by the user is prime. Since a number which is prime is not divisible other than 1 and the number itself, it is better to check the numbers upto half the number itself rather than checking every number upto the number. Thus, I have used this assignment statement: primeCheck = (number / 2) + 1;. The variable 'flag' is used as a flag to check condition inside the loop whether to find the prime factors of the number(if the number is not prime) or not (if the number is prime).

for ( i = 2; i < number; i++ )
{
if ((number % i))
{
flag = 1;
}
else
{
flag = 0;
break;
}
}


This is the first for loop which checks if the user entered number is prime. If that is the case we set flag as 1, else as soon as the number is found to be divisible by any number between 1 and the number itself (both exclusive) we set the flag as 0 and break out of the loop.

if (flag == 1)
printf("1 X %d", number);


Once we are out of the first for loop we check the flag. If it is found to be 1, that means the number was prime, and thus we print 1 X number as the output and return.

But if the number is not a prime? Then we use the else case. For simplicity, I will break the else case now. All the statements inside the else block have been enveloped in a for loop:
for ( i = 2; i <= primeCheck; i++ )
In this for loop, we again use the variable 'primeCheck' as the upper limit. Why did I do that? Again the reason being the fact that we need to check only the numbers upto 'primCheck'! We don't have to check the numbers beyond that because the factors need to be whole number (and thus we need to check only half of the numbers since any number bigger than 'number'/2 won't give a integral multiple of the number).


while ( !(number % i) || (number == i) )
{
printf("%d ", i);
number /= i;
if ( number > 1 )
printf("X ");
}


Now let's come to the while loop condition. (number % i) returns true if the number is not divisible by i. I have used !(number % i), i.e., the NOT of the condition, which would return true if the number is divisible by i. (number == i) returns true if the number and i are equal. If any of the two conditions is true, we execute the while loop block. Now since, !(number % i) || (number == i) means that the number is divisible by i (the first condition is explained earlier, and the second one is of course true! the number is always divisible by itself!!), thus the statement printf("%d ", i); prints i since the program flow proves 2 things, i is a prime number and a factor of 'number', thus the prime factor of 'number'. How does it prove that it is a prime factor? To answer this question you can do a little paperwork. In the loop, I am going up the loop. Thus, as soon as I find the smallest number that can divide the variable 'number' I print that number and divide the the variable 'number' by that, and continue this until that number cannot factorize the variable 'number' anymore. So in case the number is even, my loop will keep dividing it by 2 until it turns out to be odd. Thus, the possibility of any other even factor than 2 is removed. Similarly, for 3, we keep dividing the number by 3 until no more '3s' can be extracted from it's factors, thus eliminating all the multiples of '3' from the candidate of being a prime factor. Thus , only prime numbers are left and hence, we get the prime factors only. Thus, we don't need any explicit loop that feeds this loop's 'i' with a prime value only. Hence, out current system is sufficient to find the factors of the number, which are all prime. You can try some examples on paper to verify and also check the program for any erroneous output. Though in my sample runs, none of the outputs were wrong.

The next statement, number /= i; divides the number by 'i' so that we are left with the rest of the number and we are not stuck in an infinite loop of printing the same prime factor again and again.

The next statement,
if ( number > 1 )
printf("X ");

prints an X followed by a space. This improves readability of the output, separating each prime factor by an X. We print this only if the number is greater than 1. If the last division of dividing the number by i resulted in 1, we don't wish to print an extra X or space between the last factor found and nothing. Thus this statement is just meant for improved readability of the program output.

system("pause") -> This statement is used to pause the program, until user presses a key. This function is not necessary in your program, I use it to see my outputs paused. If you use cmd to run your programs, you might not need this. If you use linux/unix you might not need this. Depending on your compiler, this function may or may not work. Moreover, removing this line of code from this program, doesn't affect the functionality of the program.

Output(s)



No comments:

Post a Comment

Need help?