you can write a naive program that computes PrimeFactor(x) by brute force. it will be slow but it will work. let's call this ProgramA.

Ah, that's a good way to think about it. Thanks!