HIGHEST COMMON FACTOR

1. Member
Join Date
Dec 1969
Posts
82

## 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.

2. Senior Member
Join Date
Dec 1969
Posts
16,931

## Yeah, a supercomputer...

There is an entire community specialising in finding factors of numbers. Specifically, finding if numbers have NO factors. In fact, there&#039;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>&#060;%<BR>For sngCounter = 2 to sngFirstNumber<BR> sngResult = sngFirstNumber MOD sngCounter<BR> if sngResult = 0 then<BR> &#039; Store sngCounter - it&#039;s a factor<BR> end if<BR>Next<BR>%&#062;<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 computer-intensive set of things to do. If you&#039;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&#039;t try and do this using ASP or a VB COM object. It&#039;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&#039;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.

3. Junior Member
Join Date
Dec 1969
Posts
10

## RE: Yeah, a supercomputer...

Craig Craig Craig... You&#039;re not thinking 4th dimentionally!<BR><BR>We just need to attack this in a different way.. We&#039;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!

4. Member
Join Date
Dec 1969
Posts
82

## 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>&#060;%<BR>If Request.QueryString("one") = "" or Request.QueryString("two") = "" then<BR>Response.Write "no querystrings"<BR>Response.End<BR>End if<BR>%&#062;<BR><BR>&#060;%<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&#062;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>%&#062;<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!

5. Senior Member
Join Date
Dec 1969
Posts
16,931

## As I said...

...it&#039;s just not feasible using an ASP page. In fact, I&#039;m surprised it didn&#039;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&#039;t know... Personally, I wouldn&#039;t. I don&#039;t know whose server you used to do that, but it&#039;s gonna die with two or more people using it concurrently :)<BR><BR>Craig.

6. Senior Member
Join Date
Dec 1969
Posts
16,931

## Try this...

&#060;%<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 (sngSecondNumber-1)<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) &#062; sngHighestFactor then sngHighestFactor = CSng(varDictionaryItem)<BR> end if<BR> Next<BR> <BR> ReturnHighestFactor = sngHighestFactor <BR> <BR>End Function<BR><BR>%&#062;<BR><BR>Then it&#039;s a matter of:<BR>&#060;%<BR>StoreFirstNumber 10855<BR>StoreSecondNumber 8065<BR>Response.Write ReturnHighestFactor<BR>%&#062;<BR><BR>You can see if that speeds it up any... But I doubt it&#039;s gonna give you an amazing increase.<BR><BR>Craig.

7. Senior Member
Join Date
Dec 1969
Posts
16,931

## Obviously....

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

8. Member
Join Date
Dec 1969
Posts
82

## 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 Tool-Pack. 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&#039;s probably why I avoided the timeout as there was no competition for resources.

9. Senior Member
Join Date
Dec 1969
Posts
16,931

## If that's the case...

...then why not make it into a simple VB executable?<BR><BR>It&#039;s very simple code - especially if you take the code I posted above. Would get you some speed increase.<BR><BR>Craig.

10. Senior Member
Join Date
Dec 1969
Posts
102

## RE: As I said...

This is rapid if you make sure the numbers are passed the right way round :<BR><BR>&#060;%<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 & "&#060;/br&#062;" & x & ":" & xx<BR><BR>Function gcd(ByVal lowest , ByVal highest)<BR>&#039; bug out if necessary, otherwise will probably time out<BR>if lowest &#062; highest then exit function<BR>Dim g, t, a<BR><BR> If (lowest &#062; highest) Then<BR> While (lowest Mod highest &#060;&#062; 0)<BR> t = lowest Mod highest<BR> lowest = highest<BR> lowest = t<BR> Wend<BR> g = highest<BR> else<BR> While (highest Mod lowest &#060;&#062; 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>%&#062;<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
•