Thread: expressing positive integers as the product of primes

  1. #1
    Registered User
    Join Date
    Oct 2002
    Posts
    33

    expressing positive integers as the product of primes

    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
    Last edited by m712; 11-04-2002 at 02:26 AM.

  2. #2
    Code Monkey Davros's Avatar
    Join Date
    Jun 2002
    Posts
    812
    >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.
    OS: Windows XP
    Compilers: MinGW (Code::Blocks), BCB 5

    BigAngryDog.com

  3. #3
    Registered User
    Join Date
    Aug 2002
    Posts
    170
    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.
    Best Regards,

    Bonkey

  4. #4
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    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
    Last edited by elad; 11-04-2002 at 11:33 AM.

  5. #5
    Registered User
    Join Date
    Dec 2001
    Posts
    27

    Prime Factors

    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.
    Pappy
    You learn something new everyday.

  6. #6
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    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
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  7. #7
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    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.
    Last edited by Hunter2; 11-04-2002 at 05:14 PM.
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Link List math
    By t014y in forum C Programming
    Replies: 17
    Last Post: 02-20-2009, 06:55 PM
  2. find the totals of positive and negative integers
    By noaksey in forum C Programming
    Replies: 5
    Last Post: 05-11-2004, 01:59 PM
  3. Help with homework please
    By vleonte in forum C Programming
    Replies: 20
    Last Post: 10-13-2003, 11:16 AM
  4. how to handle integer overflow in C
    By kate1234 in forum C Programming
    Replies: 8
    Last Post: 04-23-2003, 12:20 PM
  5. Positive integers
    By cxs00u in forum C++ Programming
    Replies: 1
    Last Post: 03-19-2002, 06:11 PM