Printable View
I need to write a c++ program that expresses a positive integer (between 1 and 1000) as a product of 2 or more prime numbers.
I know how to find the prime factors, but I'm stumped after that. I was thinking of using a bunch of if-then statements which multiply the prime factors until they equal the positive integer, but I have a hunch that there's a much simpiler method
>Mmm, never heard of the product problem before.
If you could solve the problem with huge numbers at high speed you would crack RSA PPK encryption.
You could start by finding all factors of any given number, and then check to see whether the factors are prime. This will take a lot processing power, but should be OK for numbers up to 1000.
If I am reading this correctly, you want all the primenumbers that when multiplied together the product is less that 10000?
I wouldn't think that this would be too dificult. Sounds like homework.
I would calculate all the primes from 1 to 10000. Then multiply them all together and store (or print) the ones that return a result of < 10000. Seems pretty easy unless I misunderstood the question.
rather than trying all combinations of primes numbers less than a givne number, why not look for factors first, if the factor is prime then look for any others, if the factor isn't prime, then refactor it.
for example:
num = 24
factors are 1, 2, 12, 24
is 1 prime--yes--but trivial so ignore, unless no other prime factors
is 2 prime--yes--place in prime factor array
is 12 prime--no--so factor it
factors of 12 are 1, 2, 6, 12
ignore 1
is 2 prime--yes--so place it in prime factor array
is 6 prime--no--so factor it
factors of 6 are 1, 2, 3, 6
is 1 prime--yes-- but ignore it
is 2 prime--yes--so add it to prime factor array
is 3 pime--yes so add it to prime factor array
ignore 6 as there are other prime factors of 6
ignore 12 as there are other prime factors of 12
ignore 24 as there are other prime factors of 24
end
2*2*2*3= 24
num = 34
factors are 1, 2, 17, 34
is 1 prime--yeas but trivial so ignore unless no other prime factors
is 2 prime--yes--place in prime factor array
is 17 prime--yes--place in prime factor array
ignore 34 as it is the number and there are other prime factors
2*17 = 34
Hi,
What you seem to be asking is a way to fing the prime factors of
a number.
First of all,not all numbers have 2 prime factors. Prime numbers have only themselves.(One is not considered a prime number).
One good place to start is finding all the prime numbers up to and including the the number divided by 2 (the smallest prime number) or 500 (The highest given number 1000 divided by 2).
Then, starting at the highest prime number you found and going to the lowest, divide the number in question by the prime numbers until one divides evenly(no remainder). The mod operator (%) is good for this. The prime number that divides evenly into the number in question is one of the prime factors.
The answer in the division may be the other if it is prime.
If it is not prime the repeat the process for that number.
BTW
I hope this helps and is enough to get you started.
He is looking for prime factorization (was it sarcasm when you said you've never seen anyone ask this before, Salem?).. I think it's a pretty popular problem.
My roomate (In an intro CS class), asked me to give him a problem to solve recursively a week ago.. this is the exact problem I gave him. In psuedocode, the solution is like this.
Code:prime_factor(n)
if n is prime, return list containing n
else, find factor f
return combined list of prime factors of f and n/f
I would have the program generate an array of all the primes up to 10000 (was that the max?) at program startup. Then take the number, and loop through the primes - if it's divisible by the first prime, add it to a vector, then divide the number by that prime and then check again if it's divisible, until it isn't... then go on to the next prime, and keep checking that one, and so on until the number has been divided down to 1. Then you know you've prime factorizorizerigged it.