Given a number n, write an efficient function to print all prime factors of n. For example, if the input number is 12, then output should be "2 2 3″. And if the input number is 315, then output should be "3 3 5 7″.
1) While n is divisible by 2, print 2 and divide n by 2.
2) After step 1, n must be odd. Now start a loop from i = 3 to square root of n. While i divides n, print i and divide n by i, increment i by 2 and continue.
3) If n is a prime number and is greater than 2, then n will not become 1 by above two steps. So print n if it is greater than 2.
Read full article from Efficient program to print all prime factors of a given number
1) While n is divisible by 2, print 2 and divide n by 2.
2) After step 1, n must be odd. Now start a loop from i = 3 to square root of n. While i divides n, print i and divide n by i, increment i by 2 and continue.
3) If n is a prime number and is greater than 2, then n will not become 1 by above two steps. So print n if it is greater than 2.
void primeFactors(int n){ // Print the number of 2s that divide n while (n%2 == 0) { printf("%d ", 2); n = n/2; } // n must be odd at this point. So we can skip one element (Note i = i +2) for (int 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 whien n is a prime number // greater than 2 if (n > 2) printf ("%d ", n);}
No comments:
Post a Comment