For the prediction of the trajectory you could do this:
The path of all your gravitational bodies should be deterministic. i.e. you could calculate them in advance for N frames and put their positions into a ring buffer. On every frame you then pull the positions out of this buffer and calculate the positions N frames into the future. In this way you only need additional memory but no additional CPU cycles.
For the player trajectory you can basically do the same thing as long as the thruster is not used. If the thruster is used you have to invalidate the ring buffer. As soon as the thruster is turned off you start calculating the trajectory again: maybe add 100 future frames on every frame, that should be possible as you only have to calculate it for one body (the player ship) and you can take all the gravitational information from the precomuted buffer for all celestial bodies.