Just do all of your work in an algebraic extension of the integers
Then a lot of numbers stop being prime.
*sorry, inner math geek coming out*
obligatory explanation: suppose you take the integers and toss in, say, sqrt(5). Then 5 is no longer prime, since 5 = sqrt(5)*sqrt(5), and it turns out that a whole lot of other numbers stop being prime as well, like 11 = (4 + sqrt(5))*(4 - sqrt(5)). Turns out that depending on which square root you toss in, different primes "stay" prime and others can be factored.
now return to your regularly scheduled thread