Is 2014411 Prime? I want to figure out whether the number 2014411 is prime or not.
What kind of mathematical searching tools/strategy I have?
Do I have to start from 1 and proceed to 2014410 while I found one as a divisor or any other efficient way to find it?
 A: It's not prime. The first thing I would try is to see if it's divisible by $3$, since a third of all numbers are (asterisk, asterisk). It's obviously not divisible by $5$. Maybe it's divisible by $7$ ding ding ding! $287773$.
If it wasn't, I would only go up a few more primes before asking a computer.
A: If you don't want to use a calculator or a computer, you have to rely on instinct. Guess right and you may quickly discover the prime factorization of a given number. Guess wrong and you might be forced to give up and ask a computer.
Take for instance the number $2013461$. It's not divisible by any of the first twenty primes, but it's not prime itself either. Could it be the square of a prime? It's not, actually, since $\sqrt{2013461} \approx$ $1418.96$.
Trying every prime up to $1409$ sounds like it could take a very long time by hand. Fermat came up with a method that might help in this case. Try $\sqrt{2013461 + y^2}$ for $y = 1, 2, 3, \ldots$ until you get an integer (it would really help to memorize the last two digits of the first hundred squares, e.g., 2013465 and 2013470 are obviously not squares).
And then we find $2013461 + 10^2 = 1419^2$, which, Fermat taught us, means $$2013461 = 1419^2 - 10^2 = (1419 - 10)(1419 + 10) = 1409 \times 1429.$$
This method would be of little help with $2014411$ because its prime factors, $7$, $31$, $9283$ are much farther apart. In cases like this, you're better off just going with trial division.
In the worst case scenario, the number to be factored is the square of a prime, e.g., $2036329$. But since the squares get thinner as the numbers get larger, you're likelier to run into the best case scenario of trial division: that a composite number has lots of small prime factors.
Another method that might interest you, somewhat more sophisticated but which also has its best case and worst case scenarios, is Pollard's $p - 1$ method.
A: For small numbers like 2014411 (if it fits on a 10-digit calculator, it's a small number) sometimes the best you can do is just try dividing by the primes in order, starting with the smallest primes.
As you already know, 1 is not a prime number, and you also already know it's a divisor of all integers. So dividing 2014411 by 1 doesn't tell you anything you didn't already know.
This number, 2014411, that's decimal, right? Then you also know that it's not divisible by 2, nor is it divisible by 5, just by looking at the least significant digit.
So maybe it's divisible by 3.
Okay, for divisibility by 3, you can add up the digits: 2 + 0 + 1 + 4 + 4 + 1 + 1 = 13, and that's not a multiple of 3, so 3 is also ruled out.
I don't know of any clever divisibility tests for 7, so I would just go ahead and put it to my calculator: 2014411 divided by 7 is 287773, so you're done, the number is composite.
If 2014411 was actually prime (which it is not), why would you need to go all the way up to 2014410? Half of that is 1007205, and even that is going too far. The least prime factor of a composite number can't be more than half the number.
A: As a basic search method, run through all primes between $2$ and $\sqrt{2014411}$.
The reason that you don't need to look beyond $\sqrt{2014411}$ is that if $d$ is a divisor of your number, then either $d$ or $2014411/d$ must be smaller than $\sqrt{2014411}$.
