Common factor

# Thread: Common factor

1. Senior Member
Join Date
Dec 1969
Posts
353

## Common factor

Is there any way I can find the first common factor between two numbers. For example, 91 and 221 both have a common factor of 13: dividing them by 13 makes 7 and 17. I do not want to have to cycle through the prime numbers (2,3,5,7,11,13,17,19...), because I could be working with very big numbers with very big common factors. I may have to resort to this if there is no other way.

2. Senior Member
Join Date
Dec 1969
Posts
96,118

## Have you checked out...

...the various compsci sites that are loaded with algorithms for math problems like this?<BR><BR>Found this by googling for "common factor algorithm" for example:<BR><BR>http://www.mat.bham.ac.uk/P.J.Flavell/teaching/Foundation/LectureNotes/L3p17-20.pdf<BR><BR>Wonderfully simple algorithm!<BR><BR>I learned it once--probably about 31 years ago--but senility tends to set in.<BR><BR>

3. Senior Member
Join Date
Dec 1969
Posts
353

## Thanks, Bill

Would&#039;ve asked my sister (the Maths genius), but she&#039;s away in Thailand (on a gap year, and will soon be studying Mathematics at Warwick University).

4. Senior Member
Join Date
Dec 1969
Posts
353

## P.S. Should be easy to script <eop>

..

5. Senior Member
Join Date
Dec 1969
Posts
96,118

## Trivial, since you have...

...a modulo capability in both JS and VBS.<BR><BR>In VBS, you can get the *integer* quotient and the remainder via:<BR><BR> quotient = dividend divisor<BR> remainder = dividend MOD divisor<BR><BR>In JS you&#039;ll have to apply Math.int() to get the integer value. Whoopee.<BR><BR>

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•