Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$\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|improve this question
    
Actually, I have a feeling my first statement is false, let x = 3. –  Leonardo Jan 25 '13 at 8:10
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.