Suppose we want to use trial division to check if n=1,429,427n=1,429,427 is prime.

We would start by trying to divide nn by 2. If that yields an integer, then we know nn must be composite, and we are done.

If that does not yield an integer, then we proceed to try and divide nn by 3. If that yields an integer, then we know nn must be composite, and we are done.

If that does not yield an integer, this process continues...

What is the largest integer that we could possibly need to try to divide nn by?

Note: we are asking for the number that we know for sure where can stop the trial division, before we even start.

Select one:

1,195

19

714,713

75,233