I know/guess there aren't any algorithm that produces prime numbers without an ever increasing algorithmic complexity.
But are there any successful attempts to produce a single algorithm that is close to prime? I mean an algorithm that increases similar to primes and is as best fit. And one that doesn't grow in complexity or is close to constant in time.
Why do I want that? Well for one thing it would of course be insightful as to finding an algorithm that creates real primes but for my purpose I specifically want it to be able to compare result I get for real primes with result I would get for faux primes (meaning something that just grows similar to primes).