# If I am checking for $s$ divides $n$ on the interval $S = [3, n-x]$, how large can I make $x$ to ensure I have verified $n$ is prime?

$\forall x \in \mathbb{Z}^+$, $x > 1 \longrightarrow x-2$ does not divide $x$

I have not yet proven this, which might be a good aside for my discrete math.

One of my current assignments in computer science asks me to calculate primes, so I thought about it and the assignment says one method is to check from $[3, n-1]$

However, I have a feeling I can find all the primes checking $[3, n-2]$

Say I want to check the interval $[3, n-x]$

How large can $x$ be to have an interval which will ensure I do not miss any primes?

-
Actually, I have a feeling my first statement is false, let x = 3. –  Leonardo Jan 25 '13 at 8:10

You can check upto $\sqrt{n}$ instead, which is better than what you are proposing. If n doesn't have a divisor less than $\sqrt{n}$, it has no divisors.