একটা পূর্ণ সংখ্যাকে আমরা এভাবে represent করতে পারি
40=2^3*5
দেখুন সব প্রাইম নাম্বার কেননা যৌগিক সংখ্যা মাত্রই কত গুলো মৌলিক সংখ্যার সমষ্টি।
কোন যৌগিক সংখ্যার বর্গমূলের সমান বা ছোট কত গুলো প্রাইম ফ্যাক্টর থাকবেই (সিভের অ্যালগরিদম)। এটাই হচ্ছে prime factorization এর মূল বিষয়।
sqrt(114)=10
তাহলে 114 এরে প্রাইম ফ্যাক্টর গুলো ২ - ১০ এর মধ্যেই থাকবে এর বাইরে যাবে না । আমাদের কাজ হচ্ছে ২-১০ পর্যন্ত যতগুলো প্রাইম নাম্বার আছে সেগুলো দিয়ে ১১৪ কে ভাগ করে দেখা যদি ভাগশেষ শূন্য হয় তাহলে তাহলে ওই সংখ্যাটি ১১৪ এর প্রাইম ফ্যাক্টর এভাবে ১০ পর্যন্ত চেক করা এর পর
114 = (114/2) = 57 , NOW, 57 / 3 = 19, Then, 19. 19 is prime so no need to check
So, 2*3*19. is the prime factor of 114.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /// Program to print all prime factors | |
| # include <stdio.h> | |
| # include <math.h> | |
| void primeFactors(int n); | |
| int main() | |
| { | |
| int n; | |
| while(scanf("%d",&n)==1){ | |
| primeFactors(n); | |
| } | |
| return 0; | |
| } | |
| // A function to print all prime factors of a given number n | |
| void primeFactors(int n) | |
| { | |
| // Print the number of 2s that divide n | |
| while (n%2 == 0){ | |
| printf("%d ", 2); | |
| n = n/2; | |
| } | |
| int i; | |
| // n must be odd at this point. So we can skip one element (Note i = i +2) | |
| for ( i = 3; i <= sqrt(n); i = i+2) | |
| { | |
| // While i divides n, print i and divide n | |
| while (n%i == 0) | |
| { | |
| printf("%d ", i); | |
| n = n/i; | |
| } | |
| } | |
| // This condition is to handle the case when n is a prime number | |
| // greater than 2 | |
| if (n > 2) | |
| printf ("%d ", n); | |
| } | |
 |
| Prime Factorization Flow chart |
