Project Euler #70: Totient Permutations

My initial thought was to exclude all primes from the search through 1<n<10^7 because, while large primes p will yield very small p / phi(p) = p / (p - 1) > 1, they cannot possibly satisfy the permutation requirement (since in terms of digits p and phi(p) = p - 1 will always differ in the rightmost digit).

Around that time it occurred to me to also rule out all even numbers because a divisor of 2 will make n / phi(n) greater than or equal to 2 (see the prev. problem for my notes on how n / phi(n) simplifies), and we know n / phi(n) can be made much smaller than 2 while still satisfying the permutation requirement (see the example of n = 87109).

Note from the formula used in the last problem,

n / phi(n) = p / phi(p)     (where p is the product of the primes dividing n),

I obtained and used the shortcut phi(n) = [n * phi(p)] / p which allows us to compute phi(n) without ever finding the full prime factorization of n (including prime power divisors).

Also, when checking primality and when finding all prime divisors of a number n, I used and built onto an ever-growing list of primes less than n... as opposed to checking EVERY number less than n for divisibility and then primality. This saved time.

Thus my method was brute-force albeit with just about every possible shortcut built in. It runs in less than 40 seconds. Ans.: 8319823

***Typo: It's obviously not true that if d divides n then d <= sqrt(n) (just take d=n). I just meant to indicate the usual bound for finding all divisors of n - one need only check up to sqrt(n) if each time one finds a divisor d one also logs n / d. This is a well known fact.