Member Avatar for ankushbansal89

i have recently started to learn c programming. while learning i came across a problem in which we are supposed to find the product of divisor of numbers of range upto 10^6.
so, plz if someone can give me any direction on this problem.

  • 3 Contributors
  • 3 Replies
  • 99 Views
  • 13 Hours Discussion Span
  • Latest Post Latest Post by ankushbansal89

Dani AI

Generated

A clean math shortcut avoids enumerating divisors: if n has d(n) divisors then the product of all divisors equals n^{d(n)/2}. With n = product p_i^{e_i} we have d(n) = product (e_i+1), and the exponent of each prime in the full product is e_i * d(n) / 2, which is always an integer (when d(n) is odd every e_i is even).

Practical algorithm for n up to 10^6:

  • Precompute smallest-prime-factor (SPF) for every integer up to 10^6 with a linear or modified Eratosthenes sieve.
  • For each queried n, factorize quickly using SPF to get (p_i,e_i).
  • Compute d = product(e_i+1).
  • For each (p_i,e_i) compute exp = e_i * d / 2 and accumulate p_i^{exp} into the result.
SPF = sieve(limit=1_000_000)
for each n:
  factors = factorize(n, SPF)   # list of (p,e)
  d = product(e+1 for (_,e) in factors)
  result = 1
  for (p,e) in factors:
    exp = e * d // 2
    result *= pow(p, exp)       # use big-int or modular pow

Implementation notes and pitfalls:

  • The final integer is enormous; use arbitrary-precision arithmetic when exact value is required. If the problem asks for the result modulo M, compute each prime contribution with modular exponentiation and, if M is prime, reduce the exponent modulo M-1 (apply Euler/Fermat carefully only when conditions hold).
  • For n <= 10^6 SPF and factorization fit in memory and are fast; precompute once and reuse. Use 64-bit integers for intermediate d and exp computations (they fit comfortably for this limit), but switch to big-int only for the final accumulation if needed.

This addresses 's range concern with an O(limit log log limit) precompute plus fast per-number factoring. 's point about big-number support is relevant for exact output; 's data-structure practice is useful, but a simple SPF+array approach is the most efficient here.

Recommended Answers

All 3 Replies

Member Avatar for Member #46692

Well if you can't calculate those number using your standard compiler use a library such as the GMP etc.

Member Avatar for csurfer

iamthwee is right but if the intention of your tutor is to make you try such things by using programming constructs then you may try using linked list to solve your problem.

Member Avatar for ankushbansal89

iamthwee is right but if the intention of your tutor is to make you try such things by using programming constructs then you may try using linked list to solve your problem.

linked list is a good option but main problem is how to compute divisors for such a large numbers. For numbers upto the range 10^3 we can compute by check all number starting from 2 to [number/2]....


But for number greater then 10^3 complexity increase and acc. to me it is not a good approach .

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.