Write a Program to find all Prime Factors of number in C
- Program Description:
- What are the Prime Factors of a Number?
- Example Input and Output:
- Program Pre-Requisites:
- Program to Calculate Prime Factors in C Language Algorithm:
- Normal Method: Calculate the Prime Factors of a Number in C using While loop:
- Efficient Method – Prime Factors in C using Square root method:
- Generate all Prime Factors in C using For loop:
- Related Programs:
Program Description:
We have looked at the Factors of number program, and GCD Program in earlier posts, In today’s post we are going to write a program to calculate all Prime Factors in C language using the Loops. The program should accept a positive number from the user and provide all Prime Factors of the given number.
What are the Prime Factors of a Number?
Prime Factors of a number are the prime numbers multiplied together to make the given number.
So The Prime factors are factors of the original number but the factors must also be prime numbers. ( Prime Factors).
Here are a few examples of Numbers and their Prime Factors.
| Number | Prime Factors |
|---|---|
| 70 | 2, 5, 7 |
| 100 | 2, 5 |
| 789 | 3, 263 |
| 45 | 3, 5 |
Example Input and Output:
Input:
Enter a Number to calculate Prime Factors: 78
Output:
Prime Factors of 78 are : 2 3 13
Program Pre-Requisites:
It is recommended to know the C Loops and Modulus Operators. Please go through the following articles to learn more about them.
Program to Calculate Prime Factors in C Language Algorithm:
In Nutshell, We need to find all Factors of the given number and then check if the factor is a prime number or not. If the factor is a prime number, Then said factor is a prime factor.
- Take input from the user and store it in variable num
- Check if the num is less than 1(As the prime numbers start from 2). If so display the error message. Invalid Input, Please try again
- Now find all factors of the number num. By checking all numbers from 1 to num (i<=num), which evenly divides the num. If the i evenly divides the num, Then i is Factor of num.
- Once we got the Factor, Then we need to check if the factor is a prime Number. To check factor is a prime number, use any of the below methods
- We can use the Normal method to check the prime number – which checks all numbers from 2 to n/2.
- Efficient Square root method to check the prime number – which checks only the numbers from 2 to sqrt(n) numbers
- If the factor is Prime number, Then display it on the console. Otherwise, go to the next iteration.
- The loop continues until the condition i<=num becomes False
Normal Method: Calculate the Prime Factors of a Number in C using While loop:
We are going to use the normal method to check the prime numbers, i.e to check all numbers from the 2 to n/2.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
/* Program: Prime Factors of a Number in C using while Author: sillyCodes.com */ #include<stdio.h> int main() { int num, i=2; // Take the input from the user printf("Enter a Number to calculate Prime Factors: "); scanf("%d", &num); // up to '1'. if(num <= 1) { printf("Invalid Input, Please try again \n"); return 0; } printf("Prime Factors of %d are : ", num); // Loop upto 'num' while(i<=num) { // Factor of number is which evenly divide the 'num' if(num % i == 0) { // 'i' is factor // Let's check if 'i' is Prime number // reset flag for every factor. // FLAG to verify the prime. int FLAG = 1, cnt; for(cnt=2; cnt<=i/2; cnt++) { if(i%cnt == 0) { // Not prime, Update FLAG FLAG = 0; break; } } // If FLAG is still 1, Then 'i' is prime. if(FLAG == 1) { // 'i' is prime factor. print it. printf("%d ", i); } } // increment counter 'i' i++; } printf("\n"); return 0; } |
Program Output:
Compile the program using your favorite compiler. We are using the GCC compiler here.
gcc prime-factors-normal.c
The above command generates the executable file named a.out. Run the executable.
📢 Learn more – Compile and Run C Programs in Linux
Positive number Test Cases:
|
1 2 3 4 5 6 7 8 9 10 |
$ ./a.out Enter a Number to calculate Prime Factors: 100 Prime Factors of 100 are : 2 5 $ ./a.out Enter a Number to calculate Prime Factors: 70 Prime Factors of 70 are : 2 5 7 $ ./a.out Enter a Number to calculate Prime Factors: 1000 Prime Factors of 1000 are : 2 5 $ |
We are getting the expected output.
Let’s test the negative number Test cases:
|
1 2 3 4 5 6 7 |
$ ./a.out Enter a Number to calculate Prime Factors: -25 Invalid Input, Please try again $ ./a.out Enter a Number to calculate Prime Factors: -34 Invalid Input, Please try again $ |
As expected, the program is displaying the error message on Invalid numbers like Negative numbers.
Efficient Method – Prime Factors in C using Square root method:
In this method, We are going to calculate the Prime Factors of number using the Square root method.
We are going to use the sqrt function from the math.h header file.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
/* Program: Prime Factors of a Number in C Efficient Method Author: sillyCodes.com */ #include<stdio.h> #include<math.h> int main() { int num, i=2; // Take the input from the user printf("Enter a Number to calculate Prime Factors: "); scanf("%d", &num); if(num <= 1) { printf("Invalid Input, Please try again \n"); return 0; } printf("Prime Factors of %d are : ", num); // Loop upto 'num' while(i<=num) { // Factor of number is which evenly divide the 'num' if(num % i == 0) { // 'i' is factor // Let's check if 'i' is Prime number // reset flag for every factor. int FLAG = 1, cnt; for(cnt=2; cnt<=sqrt(i); cnt++) { if(i%cnt == 0) { // Not Prime. Update 'FLAG' FLAG = 0; break; } } // If FLAG is still 1, Then 'i' is prime. if(FLAG == 1) { // 'i' is prime factor. print it. printf("%d ", i); } } // increment counter 'i' i++; } printf("\n"); return 0; } |
Program Output:
As we used the library function sqrt, We need to pass the -lm (math.h’s is implemented as part of the libm.solibrary) option to GCC.
Otherwise, we get the linking error. Here is an example, Without passing the -lm option.
|
1 2 3 4 5 |
$ gcc prime-factors-2.c /usr/bin/ld: /tmp/ccpdUZjr.o: in function `main': prime-factors-2.c:(.text+0xed): undefined reference to `sqrt' collect2: error: ld returned 1 exit status $ |
As you can see from the above output, We got the Linking error. To overcome the linking error, We need to pass the -lm option.
$ gcc prime-factors-2.c -lm
The above command is executed without any error and the executable file a.out is generated.
Run the program.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
$ ./a.out Enter a Number to calculate Prime Factors: 48 Prime Factors of 48 are : 2 3 $ ./a.out Enter a Number to calculate Prime Factors: 126 Prime Factors of 126 are : 2 3 7 $ ./a.out Enter a Number to calculate Prime Factors: 99 Prime Factors of 99 are : 3 11 $ ./a.out Enter a Number to calculate Prime Factors: -23 Invalid Input, Please try again $ ./a.out Enter a Number to calculate Prime Factors: -067 Invalid Input, Please try again $ ./a.out Enter a Number to calculate Prime Factors: 0875 Prime Factors of 875 are : 5 7 $ ./a.out Enter a Number to calculate Prime Factors: 4567 Prime Factors of 4567 are : 4567 $ |
Generate all Prime Factors in C using For loop:
Let’s re-write the above program using the for loop instead of the while loop.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
/* Program: Prime Factors of a Number in C Efficient Method using for loop Author: sillyCodes.com */ #include<stdio.h> #include<math.h> int main() { int num, i; // Take the input from the user printf("Enter a Number to calculate Prime Factors: "); scanf("%d", &num); if(num <= 1) { printf("Invalid Input, Please try again \n"); return 0; } printf("Prime Factors of %d are : ", num); // Loop from '2' to 'num' for(i=2; i<=num; i++) { // Factor of number is which evenly divide the 'num' if(num % i == 0) { // 'i' is factor // Let's check if 'i' is Prime number // reset flag for every factor. int FLAG = 1, cnt; for(cnt=2; cnt<=sqrt(i); cnt++) { if(i%cnt == 0) { // Not Prime. Update 'FLAG' FLAG = 0; break; } } // If FLAG is still 1, Then 'i' is prime. if(FLAG == 1) { // 'i' is prime factor. print it. printf("%d ", i); } } } printf("\n"); return 0; } |
Program Output:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
$ gcc prime-factors-2.c -lm $ ./a.out Enter a Number to calculate Prime Factors: 456 Prime Factors of 456 are : 2 3 19 $ ./a.out Enter a Number to calculate Prime Factors: 789 Prime Factors of 789 are : 3 263 $ ./a.out Enter a Number to calculate Prime Factors: 47 Prime Factors of 47 are : 47 $ ./a.out Enter a Number to calculate Prime Factors: 45 Prime Factors of 45 are : 3 5 $ ./a.out Enter a Number to calculate Prime Factors: -98 Invalid Input, Please try again $ ./a.out Enter a Number to calculate Prime Factors: -5 Invalid Input, Please try again $ |
Related Programs:
- If else practice Programs
- Switch Case Practise Programs
- C program to test Leap year
- C program to Find Area and Perimeter of Rectangle.
- Calculate the Grade of Student.
- Temperature Conversion program in C. ( Centigrade to Fahrenheit ).
- Type Conversion Operators on Assignment operator.
- Prime Numbers up to n
- Calculate Sum of Digits Program in C
- Octal to Decimal Number Conversion
4 Responses
[…] C Program to find all Prime Factors of number […]
[…] C Program to find all Prime Factors of number […]
[…] C Program to find all Prime Factors of number […]
[…] C Program to find all Prime Factors of number […]