On Fri, Jul 13, 2018 at 10:56:21AM +1000, Chris Angelico wrote:
You can say that about algorithms easily enough. My point is that this ought to be a constraint on the function - implementations may choose other algorithms, but they MUST follow one pattern or the other, meaning that a Python script can depend on it without knowing the implementation. Like guaranteeing that list.sort() is stable without stipulating the actual sort algo used.
I cannot imagine an algorithm that wasn't totally brain-dead (like "flip a coin") which could wrongly report a prime number as composite. Maybe I'm not imaginative enough :-)
But yeah, if you want to formally specify that any such isprime test will never have false negatives (never report an actual prime as composite), sure thing. I think that's stating the bleeding obvious, like demanding that any algorithm we use for factorial(n) must not return the sqrt of n by mistake, but whatever :-)
I suppose that if you cared more about running time than correctness, one might simply report anything bigger than (let's say) 2**20 as "composite". But I call that "brain dead" :-)