How to compute GCD efficiently?
Using a linear sieve like this:

https://e-maxx-eng.appspot.com/algebra/prime-sieve-linear.html

you can factor every number in range $j=2,3,..,k-1$ in linear time.

From there, you get an array with some prime divisor (the least for example) of each number in the range. Using that you can solve your problem by filling $A$ in order, and for each new number $j$ you just use the prime divisor of it, find it's greater exponent in $a$, and $j$, and use the previously calculated results in $A$ to get your answer. I'm not totally sure this last part it runs in linear time, but it should be possible.