
HIGHEST COMMON FACTOR
Starting with two numbers, I need to be able to find the highest common integer factor of the two.<BR><BR>For example, if I had the numbers 24 and 36, the highest common factor would be 12. So 24:36 would equal 2:3.<BR><BR>However I will be generating numbers with values in excess of 10,000.<BR><BR>Can anyone suggest a good method for doing this.

Yeah, a supercomputer...
There is an entire community specialising in finding factors of numbers. Specifically, finding if numbers have NO factors. In fact, there's a distributed application whose sole purpose is to generate numbers and find if they have factors.<BR><BR>Think about it. You have to take each number, and then go from 2 to that number, seeing if it is a factor:<BR><%<BR>For sngCounter = 2 to sngFirstNumber<BR> sngResult = sngFirstNumber MOD sngCounter<BR> if sngResult = 0 then<BR> ' Store sngCounter  it's a factor<BR> end if<BR>Next<BR>%><BR>Then do the same for sngSecondNumber.<BR><BR>Then, iterate through the collection of numbers and find the highest one which occurs in both collections...<BR><BR>Bear in mind, however, that this is a SIGNIFICANTLY computerintensive set of things to do. If you're using 10,000 as one number, that alone will require (10000*99998) computations just to find all factors!<BR><BR>Then you have to do the same for the second number, and then you have to compare the lists...<BR><BR>I REALLY suggest you don't try and do this using ASP or a VB COM object. It'll just time out. You need to do this as an application with lots of DoEvents calls. REALLY.<BR><BR>By the way, you COULD reduce the number of counts, as you only need to test the prime numbers between 2 and the lowest number. Then the highest factor is (highest number / (highest common prime number * (highest number MOD highest common prime number)). I think. Just added that last bit off the top of my head.<BR><BR>Bear in mind that you'll need a LIST of these prime numbers first, so that in itself will be a problem...<BR><BR>This is a HUGE task  have you thought this through?!<BR><BR>Craig.

RE: Yeah, a supercomputer...
Craig Craig Craig... You're not thinking 4th dimentionally!<BR><BR>We just need to attack this in a different way.. We'll write a screensaver that will connect to the central ASP server, and pickup a list of calculations. Then send this data back to the ASP to store in a central database, simple!

RE: Yeah, a supercomputer...
I was thinking that it would likely be a fruitless search. I have written code that does find the factors:<BR><BR><%<BR>If Request.QueryString("one") = "" or Request.QueryString("two") = "" then<BR>Response.Write "no querystrings"<BR>Response.End<BR>End if<BR>%><BR><BR><%<BR>dim iOne, iTwo, iHCF, iLow, iHigh, iLoop, iRemainderLow, iRemainderHigh<BR>iOne = CInt(Request.QueryString("one"))<BR>Response.Write "iOne = " & iOne & "<BR>"<BR>iTwo = CInt(Request.QueryString("two"))<BR>Response.Write "iTwo = " & iTwo & "<BR>"<BR><BR>If iOne = iTwo then<BR>iHCF = iOne<BR>Response.Write "Highest Common factor of " & iOne & " and " & iTwo & " = " &iHCF<BR>Response.End<BR>End if<BR><BR>If iOne>iTwo then<BR>iLow = iTwo<BR>iHigh = iOne<BR>Else<BR>iLow = iOne<BR>iHigh = iTwo<BR>End if<BR><BR>Response.Write "iLow = " & iLow & "<BR>"<BR>Response.Write "iHigh = " & iHigh & "<BR>"<BR><BR>For iLoop = iLow to 1step 1<BR>iRemainderLow = iLow mod iLoop<BR>iRemainderHigh = iHigh mod iLoop<BR>Response.Write "iLoop = " & iLoop & "<BR>"<BR>Response.Write "iLow mod iLoop = " & iRemainderLow & "<BR>"<BR>Response.Write "iHigh mod iLoop = " & iRemainderHigh & "<BR>"<BR>Response.Flush<BR>If iRemainderLow = 0 and iRemainderHigh = 0 then<BR>iHCF = iLoop<BR>Response.Write "Highest Common factor of " & iOne & " and " & iTwo & " = " & iHCF<BR>Response.End<BR>End if<BR>Next<BR>%><BR><BR>But it takes forever with big numbers! A test with 10255 and 8465 took 4 minutes, but gave the right answer of 5!

As I said...
...it's just not feasible using an ASP page. In fact, I'm surprised it didn't time out on you!<BR><BR>If you had it as a VB program, then you would probably get some speed increase (but minimal, I would expect), and you would lose the problems of timeouts.<BR><BR>If you want to do it on the web... Then I don't know... Personally, I wouldn't. I don't know whose server you used to do that, but it's gonna die with two or more people using it concurrently :)<BR><BR>Craig.

Try this...
<%<BR><BR>Dim dictFirstNumberFactors: Set dictFirstNumberFactors = Server.CreateObject("Scripting.Dictionary")<BR>Dim dictSecondNumberFactors: Set dictSecondNumberFactors = Server.CreateObject("Scripting.Dictionary")<BR><BR >Sub StoreSecondNumber(sngSecondNumber)<BR> Dim sngCounter<BR> dictSecondNumberFactors.RemoveAll<BR> For sngCounter = 2 to (sngSecondNumber1)<BR> sngResult = sngSecondNumberMOD sngCounter <BR> if sngResult = 0 then <BR> dictSecondNumberFactors.Add sngCounter, 1 <BR> end if <BR> Next <BR>End Sub<BR><BR>Sub StoreFirstNumber(sngFirstNumber)<BR> Dim sngCounter<BR> dictFirstNumberFactors.RemoveAll<BR> For sngCounter = 2 to sngFirstNumber <BR> sngResult = sngFirstNumber MOD sngCounter <BR> if sngResult = 0 then <BR> dictFirstNumberFactors.Add sngCounter, 1 <BR> end if <BR> Next <BR>End Sub<BR><BR>Function ReturnHighestFactor()<BR> <BR> Dim sngHighestFactor: sngHighestFactor = 0<BR> Dim varDictionaryItem<BR> For Each varDictionaryItem in dictFirstNumberFactors<BR> if dictSecondNumberFactors.Exists(varDictionaryItem) = True then<BR> if CSng(varDictionaryItem) > sngHighestFactor then sngHighestFactor = CSng(varDictionaryItem)<BR> end if<BR> Next<BR> <BR> ReturnHighestFactor = sngHighestFactor <BR> <BR>End Function<BR><BR>%><BR><BR>Then it's a matter of:<BR><%<BR>StoreFirstNumber 10855<BR>StoreSecondNumber 8065<BR>Response.Write ReturnHighestFactor<BR>%><BR><BR>You can see if that speeds it up any... But I doubt it's gonna give you an amazing increase.<BR><BR>Craig.

Obviously....
...you need:<BR><%<BR>dictFirstNumberFactors.RemoveA ll: Set dictFirstNumberFactors = Nothing<BR>dictSecondNumberFactors.RemoveAll: Set dictSecondNumberFactors = Nothing<BR>%><BR>At the end, to clear up the objects... :)<BR><BR>Craig.

RE: As I said...
As I will only need to run the factor calculation once when a set of data is complete I think I will run it offline using something like Excel which, I beleive, has a function for this in the Analysis ToolPack. I can then manually insert the values into my DB.<BR><BR>I ran the script on my development server which is doing nothing but running my development scripts  that's probably why I avoided the timeout as there was no competition for resources.

If that's the case...
...then why not make it into a simple VB executable?<BR><BR>It's very simple code  especially if you take the code I posted above. Would get you some speed increase.<BR><BR>Craig.

RE: As I said...
This is rapid if you make sure the numbers are passed the right way round :<BR><BR><%<BR>Dim n1, n2, x, xx, hcf<BR><BR>n1 = 8465<BR>n2 = 10255<BR>hcf = gcd(n1, n2)<BR><BR>x = n1 / hcf<BR>xx = n2 / hcf<BR><BR>response.write "HCF : " & hcf & "</br>" & x & ":" & xx<BR><BR>Function gcd(ByVal lowest , ByVal highest)<BR>' bug out if necessary, otherwise will probably time out<BR>if lowest > highest then exit function<BR>Dim g, t, a<BR><BR> If (lowest > highest) Then<BR> While (lowest Mod highest <> 0)<BR> t = lowest Mod highest<BR> lowest = highest<BR> lowest = t<BR> Wend<BR> g = highest<BR> else<BR> While (highest Mod lowest <> 0)<BR> a = highest Mod lowest<BR> highest = lowest<BR> lowest = a<BR> Wend<BR> g = lowest<BR> end If<BR> gcd = g<BR> <BR>end Function<BR>%><BR><BR><BR><BR>Anglo Saxon
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

