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

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)

-

## marked as duplicate by Ｊ. Ｍ., Jyrki Lahtonen, Douglas S. Stones, Jonas Meyer, David MitraJan 1 '12 at 10:00

I hope you realize that this is one of the largest problem in mathematics today. For smaller numbers like the one you presented there are several "quick" ways as can be seen at this link: en.wikipedia.org/wiki/Primality_test but you will most surely need a calculator (unless you are willing to do all the calculations by hand). –  E.O. Jan 1 '12 at 6:40
It's a prime if you put in in wolfram alpha. –  simplicity Jan 1 '12 at 6:44
@chimpanzee: If you know how to multiply and divide with pencil and paper, there's a lot you can do with enough time. What specifically are you looking for that isn't answered by checking the remainder on division by numbers up to $\lfloor\sqrt{1937923859}\rfloor$? (Of course there are various ways to cut down the number of computations in doing so, but to me it is unclear what exactly the question is.) –  Jonas Meyer Jan 1 '12 at 7:07
@chimp: there's no such thing as a number that is "slightly prime" or "somewhat composite". The two conditions are mutually exclusive. If it's definitely not one, it's certainly the other. –  Ｊ. Ｍ. Jan 1 '12 at 7:47

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.

-
+1, this is a great answer, especially the part about 12 hours a day for 3 weeks. I believe someone in the 1800's actually factored $F_6=2^{2^6}+1$ by just spending days and days. One comment: for the start of the last big paragraph, why use $\approx$ when we can write the more precise $\leq$. Wasn't the goal of the preceeding section to show it is $\leq44021$? –  Eric Naslund Jan 1 '12 at 8:36
@Eric: Thank you. I'll edit to clarify by adding floor and inequality. $\leq$ would technically be incorrect as originally stated (without floor). –  Jonas Meyer Jan 1 '12 at 8:42
+1 @Eric, I'm fairly sure (and I believe you are, too) that whoever was working on $F_6$ was surely aware of this result. –  Jyrki Lahtonen Jan 1 '12 at 8:45
this reminds me of the story of William Shanks who 'took 15 years to calculate $\Pi$ with 707 digits, although due to a mistake only the first 527 were correct'...(en.wikipedia.org/wiki/Pi) –  user20266 Jan 1 '12 at 9:34

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

-
It's gonna be very hard to calculate with hand if I adopt that. –  chimpanzee Jan 1 '12 at 6:53
you can test a small number for primality by using divisibility rules as suggested at primes.utm.edu/prove/index.html. –  Ritesh Jan 1 '12 at 6:59
you can test a small number for primality by using divisibility rules or wheel factorization (with calculator) as suggested at primes.utm.edu/prove/prove2_1.html. –  Ritesh Jan 1 '12 at 7:07
here is a link for divisibility rule if you are going to use only 'brain power': en.wikipedia.org/wiki/Divisibility_rule –  Ritesh Jan 1 '12 at 7:11