9

To find whether N is a prime number we only need to look for all numbers less or equal to sqrt(N). Why is that? I am writing a C code so trying to understand a reason behind it.

vehomzzz
  • 42,832
  • 72
  • 186
  • 216
  • 23
    @ChssPly76: I think this is a completely valid algorithms query. – Artelius Oct 17 '09 at 22:50
  • 6
    Hmm... I am writing code to implement this. How is it not programming again? – vehomzzz Oct 17 '09 at 22:51
  • 2
    I agree, this is totally programming related. Testing primality is a very common beginner exercise, and it's quite to reasonable to want to understand why the 1..sqrt(n) method works. – bcat Oct 17 '09 at 22:53
  • 4
    Actually, you only need to check the prime numbers <= sqrt(N) :) – MartW Oct 17 '09 at 22:53
  • 1
    Personally I disagree with this closed decision... :-/ Andrej try to understang how or why something improves its algorithm. Computes are tools for many things. Math amongst many other things! – yves Baumes Oct 17 '09 at 22:54
  • With out theory, there wouldnt be any programming. Look at Rabin Miller . http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test – DarthVader Oct 17 '09 at 22:55
  • This is programming related or at least close enough – Adam Batkin Oct 17 '09 at 22:56
  • Andrei: While trial division is an easy way of prime testing and is fast for small primes, there are much faster ways of finding primes in general. Have a look at http://stackoverflow.com/questions/7272/of-ways-to-count-the-limitless-primes – Artelius Oct 17 '09 at 22:56
  • 2
    If I eat waffles while programming, do waffles become programming related? This is a math question. If the question were "how do I check for primes in C" or something, it would be programming related, but this is just "why do I only need to check sqrt(N)?" That's language agnostic. – GManNickG Oct 17 '09 at 22:57
  • the answer to your question is very easy, imagine 100, 50 is a divisor but so is 5 and 2. so you dont need to look at 50, looking at 5 and 2, is the same thing as looking at 50. and so on. – DarthVader Oct 17 '09 at 22:58
  • 1
    @GMan: I don't see the connection? There are very few programs involving waffles; but there are many programs that involve prime numbers. – Artelius Oct 17 '09 at 22:59
  • 8
    Belongs on http://mathoverflow.net. – Greg Hewgill Oct 17 '09 at 23:00
  • 1
    I guess my analogy didn't go too far. The point is, what part of the question involves programming? It's number theory, not programming. You can program it, sure, but the actual question at hand has no language, or even anything computer related to it. – GManNickG Oct 17 '09 at 23:01
  • @GMan Most of my computer science courses had nothing to do with a particular language or even computers. But they still made me a better programmer, are definitely *programming related* and still part of the CS curriculum – Adam Batkin Oct 17 '09 at 23:06
  • First program I ever wrote was for finding primes on a Casio calculator. This question has an answer, and is as language-specific as all the algorithm ones that float around here. – MartW Oct 17 '09 at 23:08
  • 2
    I don't understand how this: "To find whether N is a prime number we only need to look for all numbers less or equal to sqrt(N). Why is that?" is computer related at all. If you can explain that to me, please share. Note, saying 'I wrote a prime tester' doesn't make this nubmer theory question programming related. – GManNickG Oct 17 '09 at 23:09
  • 2
    Things are already too scattered with SO, SU and SF - plus Meta. Sending people to more places just compounds the problems. It doesn't belong on SU or SF or Meta; it is loosely related to programming (you write √N if it is a maths question!), so it belongs on SO. – Jonathan Leffler Oct 17 '09 at 23:12
  • Even if I agree with you, it still doesn't make it programming related :) – GManNickG Oct 17 '09 at 23:17
  • 3
    Like I said, it's an algorithms question (it's also a number theory question, but the algorithms answer and the number theory answer may not be the same). Maybe having a look through the chapter of Knuth's Art of Computer Programming would convince you that this stuff is relevant to programming. – Artelius Oct 17 '09 at 23:19
  • 1
    a discussion whether this sort of questions belongs here is here http://meta.stackexchange.com/questions/26339/are-algorithm-questions-allowed-on-so . Hence let's limit this question to programming answers, not meta answers – vehomzzz Oct 17 '09 at 23:20
  • 7
    GMan: By your logic, almost every question in `algorithms`, `cryptography`, `compression` and a boatload of other tags would be offtopic. At the end of the day, programming is a applied mathematical discipline - I would agree with you if the question was *"how do I **prove** that I only need to test numbers <= sqrt(N)"*. – caf Oct 18 '09 at 01:40
  • Algorithms are meant to be implemented on a computer, though. All deal with math, but are related computer inherently. This is pure math. – GManNickG Oct 18 '09 at 04:47
  • 1
    @Greg Hewgill http://mathoverflow.net/ contains more hardcore math. I doubt this simple CS-related stuff would be appropriate there. – starblue Oct 18 '09 at 06:30
  • 2
    @caf: *Proving* that an algorithm always gives the desired solution is highly programming related. In fact it's a debugging technique (labour intensive but very, *very* effective). – Artelius Oct 18 '09 at 07:11
  • 2
    Agreed, but this isn't an algorithm, it's a math problem. This would be perfectly suited on mathoverflow. The question has an implicit "proof" like caf said anyway. He's asking why, that's the same as asking for a proof. Proof just sounds different, it's the same. – GManNickG Oct 18 '09 at 07:41
  • And just to prove my point, observe the highest voted answer. Where in that answer is there anything related to programming or computers? Nowhere. Same with all the other answers. – GManNickG Oct 18 '09 at 07:42
  • 2
    This is a condition required for correctness of an algorithm. There are lots of those, you'd be trying to throw out a good part of computer science. Programming != mindless hacking. – starblue Oct 18 '09 at 09:43
  • Read the thread on meta. Joel says this isn't an algorithms question. Sorry. That's not a correctness of algorithm, it's a correctness in number theory. There's a difference. – GManNickG Oct 21 '09 at 07:28

5 Answers5

28

N is prime if it is a positive integer which is divisible by exactly two positive integers, 1 and N. Since a number's divisors cannot be larger than that number, this gives rise to a simple primality test:

  • If an integer N, greater than 1, is not divisible by any integer in the range [2, N-1], then N is prime. Otherwise, N is not prime.

However, it would be nice to modify this test to make it faster. So let us investigate.

Note that the divisors of N occur in pairs. If N is divisible by a number M, then it is also divisible by N/M. For instance, 12 is divisble by 6, and so also by 2. Furthermore, if M >= sqrt(N), then N/M <= sqrt(N).

This means that if no numbers less than or equal to sqrt(N) divide N, no numbers greater than sqrt(N) divide N either (excepting 1 and N themselves), otherwise a contradiction would arise.

So we have a better test:

  • If an integer N, greater than 1, is not divisible by any integer in the range [2, sqrt(N)], then N is prime. Otherwise, N is not prime.

if you consider the reasoning above, you should see that a number which passes this test also passes the first test, and a number which fails this test also fails the first test. The tests are therefore equivalent.

Artelius
  • 48,337
  • 13
  • 89
  • 105
6

A composite number (one that is not prime, or 1) has at least 1 pair of factors, and it is guaranteed that one of the numbers from each pair is less than or equal to the square root of the number (which is what you are asking about).

If you square the square root of the number, you get the number itself (sqrt(n) * sqrt(n) = n), so if you made one of the numbers bigger (than sqrt(n)) you would have to make the other one smaller. If you then only check the numbers 2 through sqrt(n) you will have checked all of the possible factors, since each of those factors will be paired with a number that is greater than sqrt(n) (except of course if the number is in fact a square of some other number, like 4, 9, 16, etc...but that doesn't matter since you know they aren't prime; they are easily factored by sqrt(n) itself).

Adam Batkin
  • 51,711
  • 9
  • 123
  • 115
5

The reason is simple, any number bigger than the sqrt, will cause the other multiplier, to be smaller than the sqrt. In such case, you should have already check it.

Tom
  • 151
  • 4
3

Let n=a×b be composite.

Assume a>sqrt(n) and b>sqrt(n).

a×b > sqrt(n)×sqrt(n)

a×b > n

But we know a×b=n, therefore a<sqrt(n) or b<sqrt(n).

Since you only need to know a or b to show n is composite, you only need to check the numbers up to sqrt(n) to find such a number.

Sam Harwell
  • 97,721
  • 20
  • 209
  • 280
0

Because in the worst case, number n can be expresed as a2.

If the number can be expressed diferently, that men that one of divisors will be less than a = sqrt(n), but the other can be greater.

Sinan Ünür
  • 116,958
  • 15
  • 196
  • 339
Luka Rahne
  • 10,336
  • 3
  • 34
  • 56