A quick way, say in a minute, to deduce whether $1037$ is a prime number

Solution 1:

$u\mid v$ is read as "$u$ divides $v$" and $u\nmid v$ is read as "$u$ does not divide $v$."

Obviously $2\nmid 1037$ since it has an odd last digit.

By the "Divisibility by $3$ Rule," it follows that $3\nmid 1037$ since $3\nmid 1+0+3+7=11$.

Obviously $5\nmid 1037$ since the last digit is not $0$ nor $5$.

If $7\mid 1037$ then $7\mid 1037-7=1030$ but $1030=103\times 10$, and $103$ is prime and $7\nmid 10$.

If $11\mid 1037$ then $11\mid 1037-77=960$ but $960=96\times 10$ and $11\mid 99$ so $11\nmid 96$ since it is off by a remainder of $3$ (and obviously $11\nmid 10$).

Try for $13$ this time, and then for $17$. You will see that it works for $17$, which indicates that $17\mid 1037$ and $1037$ is not prime.

You can try this method for all numbers, and you only need to try the first prime numbers less than the square root of the number you are testing with; for example, say you don't know if $61$ is a prime number. Then, apply this method.

Now, $64=8^2$ so $\sqrt{61}$ is pretty close to $8$. And since $7^2=49<61$, then all you need to do is see if $2,3,5$ or $7$ divide $61$. If they don't, then $61$ is prime (which it is).

This method does not have an official name, so it might as well be called a "trial divisibility check" by primes. Thanks to users that commented below who corrected me as I thought this method was the following.

A well known method is the "Sieve of Eratosthenes."

Tip:

A good number of primes to remember off the top of your head is all of the primes up to $127$. This has helped me, and $127$ is a pretty special number. There are many good properties about $127$; for example, $127$ is a Mersenne prime (a prime of the form $2^p-1$ for prime $p$), and it is the $31$st prime number, $31$ also being a Mersenne prime.

If you want to remember more prime numbers after $127$, you can. (I did all the way up to $383$, so it is possible.)

Apologies if this answer is primarily opinion-based.

Solution 2:

There are various methods for deciding primality, some probabilistic (the result is not sure but the more you run the algorithm the more securely you know the answer) and there are deterministic methods (they decide for sure). Altough all of these working efficiently on numbers that are way greater than $1037$.

With numbers of this size checking all numbers seems to be the most efficient way. There of course are some special cases but if you get a number of this size you should go about checking if it is even (easy), divisible by $3$ (the digitsum is divisible by $3$) by $5$ (ends with $0$ or $5$) and so on. If you have a calculator at hand it wouldn't take longer than a minute since $\sqrt{1037}\approx 32$ so you only have to check primes up to $31$.

They surely do not mean tests like these but I would like to add some links for the sake of completeness

Probablilistic test is the so called Miller-Rabin test.

And for deterministic Pollards $p-1$ and Lenstras elliptic curve factorisation is a fast and efficient one.

Even difference of squares can work fine:

$N$ is to be factored, find a $b^2$ such that $N+b^2$ is a square, say $a^2$ and then

$$ N+b^2=a^2 $$ so $$ N=a^2-b^2=(a-b)(a+b) $$

Solution 3:

I suspect the interviewer is more interested in your approach to answering the question than in the speed of your mental arithmetic. As a practical approach, I would rule out 2,3 and 5 as factors immediately and then use the calculator on my phone to check divisibility by other small primes. For 1037 you only need to check primes up to 31. But the most impotant thing is to talk through what you are doing and why you are doing it.

Solution 4:

As others have noted, you only need to check primes up to 31. Of course that'll take a while if you have to do it by long division - here's a few shortcuts.

2: The last digit isn't even, so obviously 1037 isn't divisible by 2.

3: The sum of the digits is 11, which isn't divisible by 3, so 1037 isn't divisible by 3.

5: The last digit isn't 5 or 0, so 1037 isn't divisible by 5.

7: If 1037 were divisible by 7, so would 1030. If 1030 were divisible by 7, 103 would be too. If 103 were divisible by 7, so would 110, which is $2 \cdot 5 \cdot 11$ and is therefore not divisible by 7. So 1037 isn't divisible by 7.

11: $1 - 0 + 3 - 7 = -3$, which is not divisible by 11, so 1037 isn't divisible by 11.

13: If 1037 were divisible by 13, then $1050 = 1037 + 13$ would also be. If $1050$ were divisible by 13, $105$ would be too. But $105 = 3 \cdot 5 \cdot 7$, so it isn't divisible by 13, so neither is 1037.

17: 1037 is divisible by 17 only if $1037 - 17 = 1020$ is. 1020 is divisible by 17 only if $102$ is. $102 = 2 \cdot 51 = 2 \cdot 3 \cdot 17$, so it is divisible by 17, so 1037 is divisible by 17, so 1037 isn't prime.

Note: These approaches don't do a good job of factoring - it's a bit tricky to unwind that last argument to figure out what $1037/17$ is. But if the question is just "is it prime", this should work fine.

Solution 5:

You're not likely to get even a moderately large random number to factor. In addition to the tests in the other answers, it might help (and it's cool to know) the test for $11$ - calculate the alternating sum of the digits and look for $0$.

At the next level, the fact that $1001 = 7 \times 11 \times 13$ means you can test for divisibility for all of those by calculating the alternating sum of three digit blocks, then just testing the three digit result.

Finally, $91$ is the only number less than $100$ that "looks like a prime" but isn't. That's because the evens, multiples of $3$ and $5$, $77$ and $49$ are clearly composite. The others are the numbers that look like primes.