I'm having trouble with this code, I want to make the answer in (^)and(*)

Example :

Enter number : 8
Prime factors of '8' : 2^3

Enter number : 56
Prime factors of '56' : 2^3*7

#include <stdio.h>

/* Find out the prime factors
* of a given number and print
* them on the screen */
void factorize(int n)
{
int d = 2;

if(n < 2) return;

printf("Prime factors of '%d': ", n);
/* while the factor being tested
* is lower than the number to factorize */
while(d < n) {
/* valid prime factor */
if(n % d == 0) {
printf("%d * ", d);
n /= d;
}
/* invalid prime factor */
else {
if(d == 2) d = 3;
else d += 2;
}
}

/* print last prime factor */
printf("%d\n", d);
}

#if defined TEST_DRIVER && TEST_DRIVER > 0
void factorize_test(void)
{
int i;
for(i = 0; i < 50; i++) {
factorize(i);
}
}

int main(void)
{
factorize_test();
return 0;
}
#else
int main(void)
{
int number;

do {
printf("Enter number: ");
scanf("%d", &number);
factorize(number);
} while (number > 1);

return 0;
}
#endif
6
Contributors
6
Replies
9
Views
7 Years
Discussion Span
Last Post by jephthah

Instead of outputting every time you find a prime factor you need to increment a count of the number of times you have had that prime factor. Then when you find a new prime factor output the data for the previous prime factor.

Also dont run your loop till n. Run it till square root of n

Also this branch is totally wrong-

/* invalid prime factor */
else {
if(d == 2) d = 3;
else d += 2;
}

this code will fail after prime P=7 -> 7+2 = 9, but 9 is not prime number, instead after 7, next prime factor should be 11.
http://en.wikipedia.org/wiki/Prime_number
So this approach is BAD. Instead you must save prime numbers into some array kind of

int primes[N] = {2, 3, 5, 7, 11, 13, 17,/* until N*/};

then in invalid prime factor branch just move to next prime factor in primes array.

Also this branch is totally wrong-

/* invalid prime factor */
else {
if(d == 2) d = 3;
else d += 2;
}

this code will fail after prime P=7 -> 7+2 = 9, but 9 is not prime number, instead after 7, next prime factor should be 11.
http://en.wikipedia.org/wiki/Prime_number
So this approach is BAD. Instead you must save prime numbers into some array kind of

int primes[N] = {2, 3, 5, 7, 11, 13, 17,/* until N*/};

then in invalid prime factor branch just move to next prime factor in primes array.

I dont think what you are saying is correct. The algorithm used by westsider is correct.
Yes after 7 the code will indeed produce 9 and 9 is not a prime number. But the input number will never be divisible by 9. So if the input is 27, the code will divide it first by 3 to get 9 and then again by 3 to get 3 and then again by 3. No problems here.
Similarly if the input is 34. The code divides the input first by 2 to get 17. Then it will iterate through 3,5,7,9,11,13,15 none of which divides 17. Only 17 divides 17.No problems here as well.
The method given by you is wrong. You want him to save the prime numbers in an array. So if the input number is 100, you want all the prime numbers from 1-100 to be stored in an array. But how will these numbers be generated ?
You will either use the algorithm given by westsider or some sieve algorithms...