2
$\begingroup$

Possible Duplicate:
Calculating prime numbers

The question is in the title. Is there a number that is divisible only by numbers greater than its square root? If not, why? I need this because it can speed up a calculation algorithm significantly if the answer is no.

$\endgroup$
5
  • 2
    $\begingroup$ No. See here. If $n$ has a divisor $d \geq \sqrt{n}$ then $1/d \leq 1/\sqrt{n}$ and thus $n/d \leq n/\sqrt{n} = \sqrt{n}$. $\endgroup$
    – t.b.
    Jun 19, 2011 at 18:40
  • 1
    $\begingroup$ If this is closed as a duplicate of the other question, its title should probably be changed — "Calculating prime numbers" is not a very illuminating title or a good search target. $\endgroup$
    – ShreevatsaR
    Jun 19, 2011 at 18:45
  • $\begingroup$ Thank you. I think that the reason why this might have come up before is that it can significantly reduce calculation time in any prime-finding algorithm. $\endgroup$
    – TimeCoder
    Jun 19, 2011 at 18:47
  • $\begingroup$ Note:This fact increased my program's speed exponentially $\endgroup$
    – TimeCoder
    Jun 19, 2011 at 18:57
  • 5
    $\begingroup$ Exponentially? What kind of program did you have before? $\endgroup$
    – Fabian
    Jun 19, 2011 at 19:21

3 Answers 3

Reset to default
9
$\begingroup$

If $a$ is not a prime, $b | a$ and $\sqrt a < b < a$, then $\frac a b | a$ and $1 < \frac a b < \sqrt a$. So the answer is obviously no.

$\endgroup$
7
$\begingroup$

No. Suppose that $n$ is positive. If $a > \sqrt n$ and $b > \sqrt n$ then $a b > (\sqrt n)^{2} = n$. Thus no positive number $n$ can be the product of two numbers, each of which is greater than the square root of $n$.

$\endgroup$
5
$\begingroup$

No. If $n=ab$ and $a>\sqrt{n}$, or in other words $a>\sqrt{ab}$, then by squaring both sides we have $a^2>ab$. Multiplying both sides by $\frac{b}{a}$, we have $ab>b^2$. Taking the square root of both sides, we have $\sqrt{ab}>b$, i.e. $\sqrt{n}>b$. Thus, every composite number is divisible by numbers less than its square root. In fact, the divisors of $n$ greater than $\sqrt{n}$ and the divisors of $n$ less than $\sqrt{n}$ are in bijection, by sending $d\mapsto \frac{n}{d}$.

$\endgroup$
1
  • 1
    $\begingroup$ I.e. the integer points of the hyperbola $\:xy = n\:$ are preserved by the reflection $\:(x,y)\mapsto (y,x)\:.$ $\endgroup$
    – Bill Dubuque
    Jun 19, 2011 at 22:53

Not the answer you're looking for? Browse other questions tagged .