Why over complicate it? FRACTRAN is a Turning complete language based on only one operation: multiplication. It's Wikipedia entry gives a short FRACTRAN program that finds all primes. https://en.wikipedia.org/wiki/FRACTRAN
In the words of it's inventor, John Conway:
Makes workday really easy! FRACTRAN needs no complicate programming manual. It's entire syntax can be learned in 10 seconds, and programs for quite complex and interesting functions can be written almost at once. The entire configuration of a FRACTRAN computer at any instant is a single integer - no messy "tapes" or other foreign concepts to be understood by the fledging programmer.