Loading ...
Sorry, an error occurred while loading the content.

RE Greatest Factor Less Than Root

Expand Messages
  • Jose Ramón Brox
    From: John W. Nicholson ... If N is even, factor with 2 until you get N odd. Once N is odd, you can write N as the difference of
    Message 1 of 1 , Jul 10, 2008
    • 0 Attachment
      From: "John W. Nicholson" <reddwarf2956@...>


      >Let N be a integer. How does one go about finding the largest factor,
      >c, less than the square root of a number, N^(1/2)?

      If N is even, factor with 2 until you get N' odd.

      Once N' is odd, you can write N' as the difference of two squares:

      N' = a^2 - b^2 =(a+b)(a-b)

      Then, execute the following algorithm:

      Start with a=ceil(Sqrt(N')).
      DO
      Check if b= Sqrt(a^2-N') is an integer
      if it is, END LOOP
      if it isn't, then increase a, a=a+1
      LOOP
      Largest factor of N' less than its square root = (a-b)
      (Largest factor of N' bigger than its square root = (a+b) )

      And so, you just have to remember the 2^r factor that we extracted earlier and calculate
      your result properly for N=2^r·N'.

      If you are interested in improving the algorithm, I recommend you look for some info about
      "Fermat's factorization" and other methods like the "quadratic sieve"

      Regards!
      Jose Brox
    Your message has been successfully submitted and would be delivered to recipients shortly.