How can I determine the number is prime number? [duplicate]

Question

Possible Duplicate:
How do you determine if a number is prime or composite?

Suppose I don't know that the number 1937923859 is prime number or not and I don't have any calculator. but I want to determine that the number is prime number or not. How can I do that?

Added Sorry for my poor explanation. I mean, more precisely, not using anything but only your hand.(maybe brain)

Answer 1

This is a naïve answer, posted because the OP said it was a nice answer when it was commented.

$1937923859$ is small enough where in principle you can check with pencil and paper without much ingenuity, given enough time. First you might want to estimate the square root. Notice that $1937923859=19.37923859\times 10^8$, so $\sqrt{1937923859}=\sqrt{19.37923859}\times 10^4$. You could get a good estimate of $\sqrt{19.379...}$, for example with a couple of iterations of Newton's method, or even guess and check to find that $4.4$ is pretty close, with $4.4^2=19.36$. You can get closer using the linear approximation of $\sqrt{x}$ near $x=19.36$: $$\sqrt{19.37923859}\approx4.4+\frac{1}{8.8}\cdot 0.01923859.$$ Note that this gives an overestimate, which is a good thing. (Incidentally, it actually gives the exact correct answer for the floor.) You don't want to underestimate and miss potential prime divisors, so if you're going with the guess and check method all the way, $4.41$ would be a better bet, or even $4.403$, etc, depending on how long you're willing to experiment.

Using $\lfloor\sqrt{1937923859}\rfloor\leq 44021$, or possibly some estimate larger than this, you can next start checking whether any of the numbers from $2$ to $44021$ divide $1937923859$. There are at least a few simple divisibility tests, e.g. check the last digit for $2$ and $5$, add the digits for $3$, alternately add and subtract digits for $11$. You don't need to check composite numbers, but on the other hand it isn't clear to me that checking for primality of the potential divisors as you go is worth the time saved in cutting redundancy. Simply by avoiding multiples of $2$ and $3$ you are down to dividing by about $1/3$ of the numbers; that is, you only need to check numbers congruent to $\pm 1 \textrm{ mod }6$. If you also avoid multiples of $5$ you're down to about $27\%$. That would still leave close to $12000$ divisibility checks. If you spend $12$ hours a day on this and the average divisibility check takes $1$ minute, you could finish in under $3$ weeks. But don't forget to check your work.

See the "Naïve methods" section of the Wikipedia page for Primality test for more.

Answer 2

Check out AKS primality test.
Another interesting site is Primes Pages