5
$\begingroup$

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?

$\endgroup$
9
  • $\begingroup$ There is no (non infinite) set of primes that can be used to check against any prime. In general I think a set of primes will be sufficient for checking up to the square of the largest prime in the set. So your 2-17 set would be sufficient to check up to 17^2. (of course the only checking against primes trick is sufficient but requires you to know the primes in advance, which makes it of only occasional use in prime checking code) $\endgroup$ May 23, 2014 at 12:35
  • $\begingroup$ However it is useful to check "trial divisors" which are fewer than all numbers less than $n$ but include all the primes. For example, check if 2 is a divisor, and then check all the odd numbers between 2 and $\sqrt{n}$ to see if any of them divide $n$. More details can be found in this SciComp post. $\endgroup$
    – hardmath
    May 23, 2014 at 12:41
  • $\begingroup$ Can someone confirm @RichardTingle 's "In general I think"? Because if it is true for all cases it can be used to really optimize the technique. $\endgroup$ May 23, 2014 at 15:11
  • $\begingroup$ It works because say the number 20 isn't prime because 2*10=20, 4*5=20 , 5*4=20, 10*2=20. In all cases one of the pair is below the square root of the number (4.47) and one is above. So testing against 5 and 10 is unnecessary because they are paired with 4 and 2 (of course testing 4 is also pointless as it's 2*2 but thats a seperate rule, the only thing leading me to "I think" is if both rules can be used together) $\endgroup$ May 23, 2014 at 15:14
  • $\begingroup$ Ok, I've got my head around this now; testing against all primes between 0 and n is equivalent to testing all numbers between 0 and n. So the rules can live together. I'll write an an answer when I get home if noone else does $\endgroup$ May 23, 2014 at 15:26

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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}$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .