Prime Factors

In number theory, the prime factors of a positive integer are the prime numbers that divide into that integer exactly, without leaving a remainder.

A few examples make it clear:

  The prime factors of 6 are (2, 3); since 2 x 3 = 6
  The prime factors of 12 are (2, 2, 3); since 2 x 2 x 3 = 12
  The prime factors of 100 are (2, 2, 5, 5); since 2 x 2 x 5 x 5 = 100

This is all just an introduction, to this article a friend sent me; about math, numbers and even a little baseball. (link rot) The article discusses a class of numbers called Ruth-Aaron pairs, which are consecutive numbers where the sum of their prime factors are equal. The first few Ruth-Aaron pairs are:

The name of the pairs come from the number 714, being the total number of home runs hit by Babe Ruth and 715 the number Aaron hit to surpass him; hence Ruth-Aaron PairSo I had to write my little script to find more of these. Finding prime factors is fairly straightforward. For the number you are factoring, go through the list of primes and check if each one divides it. In programming that means (num % prime == 0)

If the prime divides the number, it is a prime factor. Then divide the number by this prime factor and start over, checking the remainder for prime factors. Continue until the remainder is equal to 1. This is sometimes called reverse division. It looks something like this, for finding the prime factors of 60

2 | 60
 ----
 2 | 30
   ----
   3 | 15
     ----
      5 | 5
        ---
          1

Prime Factors: 2 x 2 x 3 x 5

Here's my python script to find Ruth-Aaron Pairs: ruth-aaron.py

It took my G5 2.0ghz PowerMac 5 hrs 3 minutes to find the 149 pairs up to 1,000,000. ruth-aaron.txt

I leave it as an exercise to re-write in C to get some real performance.

Related Links

• Ruth-Aaron Pairs on Wikipedia
• My Prime Numbers page with a few scripts on finding primes using the Sieve of Eratosthenes. The same method I use in this script to find the listing of primes.