Algorithm to calculate the number of divisors of a given number

by

Dmitriy is right that you’ll want the Sieve of Atkin to generate the prime list but I don’t believe that takes care of the whole issue. Now that you have a list of primes you’ll need to see how many of those primes act as a divisor (and how often).

Here’s some python for the algo Look here and search for “Subject: math – need divisors algorithm”. Just count the number of items in the list instead of returning them however.

Here’s a Dr. Math that explains what exactly it is you need to do mathematically.

Essentially it boils down to if your number n is:
n = a^x * b^y * c^z
(where a, b, and c are n’s prime divisors and x, y, and z are the number of times that divisor is repeated)
then the total count for all of the divisors is:
(x + 1) * (y + 1) * (z + 1).

Edit: BTW, to find a,b,c,etc you’ll want to do what amounts to a greedy algo if I’m understanding this correctly. Start with your largest prime divisor and multiply it by itself until a further multiplication would exceed the number n. Then move to the next lowest factor and times the previous prime ^ number of times it was multiplied by the current prime and keep multiplying by the prime until the next will exceed n… etc. Keep track of the number of times you multiply the divisors together and apply those numbers into the formula above.

Not 100% sure about my algo description but if that isn’t it it’s something similar .

More Related Contents:

  1. High-performance merging of ordered sets
  2. How to find the kth largest element in an unsorted array of length n in O(n)?
  3. Recursion or Iteration?
  4. How to speed up A* algorithm at large spatial scales?
  5. nth fibonacci number in sublinear time
  6. What is the fastest way to get the value of π?
  7. What are the rules for the “Ω(n log n) barrier” for sorting algorithms?
  8. Find number in sorted matrix (Rows n Columns) in O(log n) [duplicate]
  9. Has anyone actually implemented a Fibonacci-Heap efficiently?
  10. Most efficient code for the first 10000 prime numbers?
  11. How to find pair with kth largest sum?
  12. I am looking for a simple algorithm for fast DCT and IDCT of matrix [NxM]
  13. Move all odd positioned element to left half and even positioned to right half in-place
  14. How can Google be so fast?
  15. What is the best way to set a register to zero in x86 assembly: xor, mov or and?
  16. Enhanced REP MOVSB for memcpy
  17. Why is Skylake so much better than Broadwell-E for single-threaded memory throughput?
  18. What does gcc’s ffast-math actually do?
  19. What is an Efficient algorithm to find Area of Overlapping Rectangles
  20. Why is reshape so fast? (Spoiler: Copy-on-Write)
  21. JMeter : How to record HTTPS traffic?
  22. Which loop is faster, while or for?
  23. Efficient maths algorithm to calculate intersections
  24. How should I calculate Ramp-up time in Jmeter
  25. Performance optimisations of x86-64 assembly – Alignment and branch prediction
  26. Return address prediction stack buffer vs stack-stored return address?
  27. When should we use prefetch?
  28. Relative performance of x86 inc vs. add instruction
  29. Efficient sse shuffle mask generation for left-packing byte elements
  30. How can the rep stosb instruction execute faster than the equivalent loop?

Leave a Comment