If any number x does not have a factor between 2 and square root of x, it is a prime number.?

Question

why do we check for factors just till root x and not beyond that? please help

Answer 1

Yes, if any number x does not have a factor between 2 and square root of x, it is a prime number.

The proof is by contradiction. Suppose that the product mn = x. Let m be geater than or equal to sqrt x. Then n must be less than or equal to sqrt x, for the product to equal x.

But, you've already checked the numbers less than sqrt x, and found that none of them is a factor of x, so you cannot have a factor of x that is greater than or equal to sqrt x.

I'd suggest you work through a few examples. e.g.

sqrt 11 = 3.3166 (to 4 sig fig).

Since 11 is odd, 2 does not divide 11. 3 won't go into 11 either.

Any integer greater than 3 is also greater than sqrt 11, and so there is no need to check.

(Some handy hints for finding factors:

1) ignore all even numbers when trying to factorise odd numbers
2) if the sum of the digits is a multiple of three, then the number is a multiple of 3. e.g. 291 (which equals 3 x 97), 2 + 9 + 1 = 12.
Adding the integers together like that is called Fadic reduction.
3) if the sum of the digits is a multiple of 9, then the number is divisible by 9. e.g. 18 = 2 x 9, 1 + 8 = 9.
3) If the last digit is a 0 or a 5, then the number is divisible by 5.
4) If the last digit is a 0, the number is divisible by 10.
5) If, for example, the number is even AND the sum of the digits is a multiple of 9, then the number is divisible by 18 (= 2 x 9) )

Answer 2

Let's say we have a integer "n", and it isn't prime. Say that "a" is a factor of n. Then we can write n = ab, where "b" is some other integer.

Now, a and b can't BOTH be greater than the square root of n; if they were both bigger than the square root of n, then their product ab would be greater than n, and we already know it equals n.

So it must be that either a or b is equal to at most the square root of n. So n must have a factor that's less than or equal to its square root.

Since any composite integer has a factor which is less than or equal to its square root, then if we check all possibilities up to the square root of a number and can't find any factors, we know the number must be prime.

Answer 3

If no factor smaller than the square root of the number divides it, it's a prime. There is absolutely no need to check beyond that so I don't know why anyone would do it.

Answer 4

Because if there was an exact factor greater than that, then dividing it into the number would give an exact answer SMALLER than the square root, so we would have found it first, but we didn't, so there's no point in looking . . .

Pretend we are checking 131, and have found that it doesn't divide by any factor up to 11. Suppose it divided by 13, the quotient would be around 10, but we know it isn't, because we've been there. Suppose it divided by 17, the quotient would be near 8, but we've been there too.

See?

Answer 5

Th eother posters proof look good, so let's skip that part. But NOTE: it should be "less than or equal to." If you have a perfect square (like 121) you need to not only check between 2 and the sqrt(121) but you need to also check 2 and also check the square of 121 which is 11 (then you discover 121=11*11 is not a prime). So it should be check all primes (greater than or equal to 2 and less than or equal to sqrt(n)."

Often what is done on large nnumbers is to test a large number of "small divisors," like all primes less than a thousand or a million, then do what is call a Miller-Rabin test, or other things like that. You then conclude with "high probability" that the number is prime.

Answer 6

A rational number can be expressed as one number over another--a ratio, like ratio-nal. So all integers are rational, since 5, 12, 18, 25 etc. are just 5/1, 12/1, 18/1, 25/1 etc. An irrational number cannot be expressed as a ratio, like pi, the square roots of 2 and 3, and others. A trick that sometimes works is to see if the number goes on forever in decimal form. But beware! 1/3, for example, which is perfectly rational, goes on endlessly--0.3333333333333 etc. A trick that *always* works is to see if the number goes on endlessly *without repeating* in decimal form. Then it is irrational.

Answer 7

if there are no factors for the number smaller than root x, thenit will not have a factor greater than root x
(root x)^2 = x
if there is a factor greater than root x, say k, then the other factor is x/k , since k >sqrt x
x/k so the other factor is less than sqrt x which is a contradiction