Is it sufficient for a number to be a prime if it is not divisible by prime numbers smaller than it?

Question

I am student of computer science with no knowledge of maths. To write a small algorithm I searched for the solution first. There are many but almost all of them state that continue dividing the number from "2" to "root(input_number)" if at some point the remainder is zero, the number is not prime. Looking at a list of prime numbers I deduced that there is no need to divide it with every number just dividing by all the primes smaller than the number would do the trick. If that is true than Ill be needing a pre-stored set of primes to divide the input number. My 2nd question is is there such a static set (I dont know how to say it in maths, set that is same for checking every number) that is if employed in this technique will correctly tell the primeness of any number? e.g., Is {2,3,5,7,11} or {2,3,5,7,11,13,17} is enough for checking every prime?

Answer 1

There is no (non infinite) set of primes that can be used to check against any prime. However you are correct that we only need to test for remainders for prime numbers between 2 and $\sqrt{n}$ where n is the number to be tested. This is for two reasons

Checking all integers between 2 and m is equivalent to checking all prime numbers between 2 and m

This is because any non prime number can be expressed as a product of prime numbers, so if a number is exactly divisible by a non prime it is also exactly divisible by that numbers prime factors.

For example 36 is exactly divisible by 6; meaning it is also exactly divisible by 2 and 3

It is only neccesary to check up to $\sqrt{n}$

This is because numbers whose product equal the number under test (and so prove the number is not prime) always come in pairs, one above and one above the square root of the number under test. In general any such pair can be expressed as follows

$n=\sqrt{n}\frac{1}{a} \times \sqrt{n}a$

So any product which multiplies together to give n (and so shows that n is not prime) will have one of the pair above and one below $\sqrt{n}$

Answer 2

The answer to your first question is yes. If a number isn't prime (and isn't 1), it's divisible by a number other than itself and 1, which means it's divisible by the prime factors of that number.

The answer to your second question is no. No finite set of primes will suffice; for any finite set of primes, take two primes not in the set and multiply them together, and the product will be a composite number not divisible by any prime in the set.