HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Finding the largest prime factor

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
thefindinglargestfactorprime

Problem

As many people will undoubtedly recognise, this is a question in a well known series of problems that I won't name ;)

It's been a long time since I've written any F# and I'm not sure I've ever come across any canonical style guidelines so I'd like feedback on all aspects of the code.

let largestPrimeFactor (number:int64) =
    let rec inner n current =
        if (n * n) > current then
            current
        else if current % n <> 0L then
            let nextCandidate = if n = 2L then 3L else n + 2L
            inner nextCandidate current
        else
            inner n (current / n)
    inner 2L number


Usage is simply:

let largestFactor = largestPrimeFactor 999999866000004473L

// 999999937


I'm not really concerned with performance... I know about the various sieve options (Eratosthenes, Atkins) and decided that trial division for a single prime was adequate.

Solution

The names of the function and parameters inner n current don't mean anything; I suggest testFactor num factor instead. I'd also swap the two parameters so that the one that varies more (the candidate factor) appears last — this is a convention to facilitate currying.

Switching the order of the cases lets you avoid nesting conditions.

let largestPrimeFactor (number:int64) =
    let rec testFactor num factor =
        if factor * factor > num then
            num
        else if num % factor = 0L then
            testFactor (num / factor) factor
        else if factor = 2L then
            testFactor num 3L
        else 
            testFactor num (factor + 2L)
    testFactor number 2L

Code Snippets

let largestPrimeFactor (number:int64) =
    let rec testFactor num factor =
        if factor * factor > num then
            num
        else if num % factor = 0L then
            testFactor (num / factor) factor
        else if factor = 2L then
            testFactor num 3L
        else 
            testFactor num (factor + 2L)
    testFactor number 2L

Context

StackExchange Code Review Q#113426, answer score: 2

Revisions (0)

No revisions yet.