Largest prime factor: Difference between revisions

=={{header|BCPL}}==

This version creates a 2,3,5 wheel object, which is instantiated by the factorization routine.

<lang BCPL>

GET "libhdr"

LET new_235wheel() = VALOF {

LET w = getvec(1)

w!0 := 1 // accumulator

w!1 := -3 // index (negative => first few primes)

RESULTIS w

}

LET next235(w) = VALOF {

LET p3 = TABLE 2, 3, 5

LET wheel235 = TABLE 6, 4, 2, 4, 2, 4, 6, 2

LET a, i = w!0, w!1

TEST i < 0

THEN {

a := p3[i + 3]

i +:= 1

}

ELSE {

a +:= wheel235[i]

i := (i + 1) & 7

w!0 := a

}

w!1 := i

RESULTIS a

}

LET gpf(n) = VALOF {

LET w = new_235wheel()

LET d = next235(w)

UNTIL d*d > n {

TEST n MOD d = 0

THEN n /:= d

ELSE d := next235(w)

}

freevec(w)

RESULTIS n

}

LET start() = VALOF {

writef("The largest prime factor of 600,851,475,143 is %d *n", gpf(600_851_475_143))

RESULTIS 0

}

</lang>

{{Out}}

<pre>

BCPL 64-bit Cintcode System (13 Jan 2020)

0.000> The largest prime factor of 600,851,475,143 is 6857

0.001>

</pre>