Results 1 to 4 of 4

Math Help - Reducing number of divisions!

  1. #1
    Newbie
    Joined
    Jan 2011
    Posts
    2

    Smile Reducing number of divisions!

    Hi all,this is my first post on the forum. I am solving a programming problem where I need to find factors of a big number N(can be even or odd). The problem is:
    I need to test different i such that (N-i) is divisible by i+1
    For a number as large as 100 crores it would take a lot of time. And therefore I need some method by which I am able to reduce the divisions to 100000 or 1000000 at maximum. Is there any way this is possible. Any suggestions would be greatly appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member abhishekkgp's Avatar
    Joined
    Jan 2011
    From
    India
    Posts
    495
    Thanks
    1
    if a|b then a|(a+b).
    so if (i+1)|(N-i) then (i+1)|(N+1).

    so it just boils down to find the number of divisors of N+1.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2011
    Posts
    2
    Thanks a lot.. with your method the number of computations reduced from 25 crore divisions to 46000 divisions.. This forum is great..
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,693
    Thanks
    1466
    You really only need to check division by prime numbers less than \sqrt{N}. Furthermore, each time you find a prime, p, that divides N, you get "p divides into N M times" and now you can switch from finding prime divisors of N to finding prime divisors of M, still larger thah or equal to p.

    Do you want prime factors of N or all ways of factoring M? If the latter, first find the prime factors, then start combining them.

    For example, to find factors of 186, does 2 divide it? Yes, 186/2= 93. Does 2 divide 93? No. Does 3 divide 93? Yes, 93= 3(31). Does 3 divide 31? No. Does 5 divide 31? No. Since 6 is larger than sqrt{31}, we can stop there. The prime factors of 186 are 2, 3, and 31. Other factors are 1 (of course), 2(3)= 6, 2(31)= 62, and 3(31)= 93.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. divisions
    Posted in the Statistics Forum
    Replies: 1
    Last Post: November 9th 2011, 10:15 AM
  2. Replies: 15
    Last Post: May 27th 2011, 09:42 PM
  3. remainders over divisions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 21st 2010, 07:12 AM
  4. Replies: 6
    Last Post: January 9th 2010, 04:44 PM
  5. Polynomial Divisions ...help???
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: September 23rd 2009, 06:12 PM

Search Tags


/mathhelpforum @mathhelpforum