
So that suggests a strategy for finding a large prime

which is to keep trying guesses until we find one that's prime.

If it's not a prime, then we add 1 and we try again.

Because of what we know about the number of primes being finite

and the density of primes, we know that after a reasonable number of iterations

this will actually find a prime and return that value.

We could do a little better if we assume we start with an odd number

and we'll assert that X is not divisible by 2

since that is very obvious that it would be prime

and increment by 2 here.

What's missing is we need some way to do this "is prime" test.

So here is a naive way to test to the finest prime.

We're going to go through the numbers from 2 to X minus 1,

checking whether X is divisible by each of those.

If it is divisible by any of those,

that would mean that it is a composite number

and we should return False.

If we try them all and it's not divisible by any of those, well then it's prime.

So the question is: Would this work?

The possible answers are: Yes, this would work fine.

No, it's too slow because the running time is exponential in the value of X.

No because it's too slow because the running time is exponential in the size of X.

And no, because there's a silly bug in my Python code.