Not only does your prime checking function always return false; even if it were functioning properly, your main loop does not seek the input number’s factors at all, but rather just the largest prime smaller or equal to it. In pseudocode, your code is equivalent to:
foo(n):
x := 0 ;
foreach d from 1 to n step 1:
if is_prime(d): // always false
x := d
return x // always 0
is_prime(d):
not( d % 1 == 0 ) // always false
But you don’t need the prime checking function here at all. The following finds all factors of a number, by trial division:
factors(n):
fs := []
d := 2
while ( d <= n/d ):
if ( n % d == 0 ): { n := n/d ; fs := append(fs,d) }
else: { d := d+1 }
if ( n > 1 ): { fs := append(fs, n) }
return fs
The testing for divisibility is done only up to the square root of the number. Each factor, as it is found, is divided out of the number being factorized, thus further reducing the run time. Factorization of the number in question runs instantly, taking just 1473 iterations.
By construction all the factors thus found are guaranteed to be prime (that’s why no prime checking is needed). It is crucial to enumerate the possible divisors in ascending order for this to happen1. Ascending order is also the most efficient, because any given number is more likely to have smaller prime factor than larger one. Enumerating the primes instead of odds, though not necessary, will be more efficient if you have an efficient way of getting those primes, to test divide by.
It is trivial to augment the above to find the largest factor: just implement append as
append(fs,d):
return d
1
because then for any composite divisor d of the original number being factorized, when we’ll reach d, we will have already divided its prime factors out of the original number, and so the reduced number will have no common prime factors with it, i.e. d won’t divide the reduced number even though it divides the original.