Member Avatar for Rexzie

Hi fellas..this is my first post here..I am new to this 'hardcore programming' and all..I came across a problem for which I killed some time..with no fruits..It might be simple,trivial or even 'famous' for you guys..Any assistance is appreciated much.So here it goes..
Given an integer,the problem is to find the prime number combination whose product form the number since any integer can be given as a product of one or more primary numbers..
For eg..for 36,the solution would be 2,2,3,3.
Another thing..a pseudo code or algorithmic description is sufficient..thanks again..

Edited by Rexzie because: n/a
  • 3 Contributors
  • 3 Replies
  • 180 Views
  • 9 Hours Discussion Span
  • Latest Post Latest Post by Rexzie

Dani AI

Generated

Good question — this is the prime-factorization problem that mentioned and was on the right track with. The practical, efficient approach is trial division that repeatedly removes a found factor (so you never test the same divisor against the same remaining value twice). You do not need a full list of primes up to n; testing divisors up to sqrt(n) (or using a precomputed prime list up to sqrt(maxN) when factoring many numbers) is enough.

function prime_factors(n):
    factors = empty list
    if n == 0: return factors        # undefined for 0
    if n < 0:
        append -1 to factors         # optional: record sign
        n = -n
    if n == 1: return factors

    while n % 2 == 0:
        append 2 to factors
        n = n / 2

    p = 3
    while p * p <= n:
        while n % p == 0:
            append p to factors
            n = n / p
        p = p + 2

    if n > 1:
        append n to factors

    return factors

Why this works: the inner loop extracts all powers of a found prime (so you get repeated primes like 2,2,3,3). After removing factors up to sqrt(original n), any remaining n>1 must be prime. Worst-case time is about O(sqrt(n)); if factoring many numbers, use a sieve once and test only primes (much faster in aggregate). To avoid overflow in languages like C++, prefer the check p <= n / p over p * p <= n.

C++ tips and caveats: use 64-bit integers (long long / unsigned long long) for moderate inputs, store factors in std::vector<long long>, handle n<=1 and negative n explicitly, and for very large or cryptographic-sized inputs use Pollard’s Rho or a bigint library (Boost.Multiprecision / GMP) rather than naive trial division.

Recommended Answers

All 3 Replies

Member Avatar for NathanOliver

I would look up prime factorization. That should point you in the right direction.

Member Avatar for Lerner

1) Create an array of prime numbers less than or equal to the given number.
2) If the given number is prime, you're done.
3) If not find the smallest prime number that is a factor of the given number and then find the other factor associated with that prime number.
4) If the associated factor is prime, then you're done.
5) If not repeat the steps 3 and 4.

Member Avatar for Rexzie

1) Create an array of prime numbers less than or equal to the given number.
2) If the given number is prime, you're done.
3) If not find the smallest prime number that is a factor of the given number and then find the other factor associated with that prime number.
4) If the associated factor is prime, then you're done.
5) If not repeat the steps 3 and 4.

Thanks man..could have been a bit deeper & clearer though..

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.