Regarding prime numbers

[ark217]

I had a test with a question on it regarding prime numbers and was hoping someone can explain to me how I would have solved it. I got it very wrong...

Basically you have a process of "factorization" in which the input is one number and the output is comprised of the display of of all the prime numbers that when multiplied make up the input.

For instance,
36 = 2 x 2 x 3 x 3
11 = 1 x 11
etc.

I had to write a function for this.
Does anyone have any idea?

[buffbill]

Yes you could do it that way and you would end up with all the prime factors of (N), the product of which would produce the given integer.
Or you could test the given integer (N) to establish if it is prime or is not prime. If N can be evenly divided by 2 or any odd integer >2 it is not prime else it is prime. With this booleon approach you could assume that every N is prime and then test with a succession of divisors to prove the assumption wrong. There are several threads in Bytes Forum which discuss.
Hope this helps

[Duthomhas]

Read through the following
http://www.purplemath.com/modules/factnumb.htm
and/or google "prime number factorization" to make sure you have a good idea of what is going on.

Next, consider how to make a function that does exactly as the examples in the above link do.

For a hint: it is typically a good idea to have an expandable list (use a vector or a deque) of prime numbers to try factoring. You might pack your list with the first few primes:

#include <deque>
const int PRIMES[ 10 ] = { 2, 3, 5, 7, 11, 13, 17, 19, 21, 23 };
std::deque< int > primes( PRIMES, PRIMES + 10 );

Then when you find a new prime just add it to your list

primes.push_back( the_next_prime_in_the_series );

This is an iterative function. You can write it either using recursion or using a loop.

Hope this helps.

[n4nature]

- Divide the input by prime numbers, starting from 2
- If number is not divisible by 2, increment the divisor to next prime number. Repeat the process until divisor is (input number-1). If the number has been non-divisible, then the number itself is a prime number
- If the number is divisible by 2 or any other divisor in the list, then continue the same process by starting the divisor value from 2 and traversing the prime numbers list upto the value of the dividend.
- Storing the values of divisors would give the list you want.

[ark217]

Okay- thanks for the responses. I understand now.