Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$\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?

share|cite|improve this question
Actually, I have a feeling my first statement is false, let x = 3. – Leonardo Jan 25 '13 at 8:10
up vote 2 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.