View Single Post
Old 2019-03-24, 13:13   #2
CRGreathouse's Avatar
Aug 2006

2·2,969 Posts

I can improve your test. This works without assuming Lehmer's conjecture:

Let x be a positive integer.

If f(x) = x-1 return PRIME
If f(x) < x-1 return COMPOSITE
If f(x) > x-1 return UNIT

Now all you have to do is find a way to compute f(x) quickly and you're done!
CRGreathouse is offline   Reply With Quote