2
$\begingroup$

I was wondering that in the process of checking if a number is a prime number, would it be reasonable to suggest that if it cannot be divided by 2, 3, 5, 7 or 9 then it could be considered a prime number?

My maths is not the greatest so I am going off the premise that any number greater than a single digit can be divided by those 4 numbers if not a prime?

$\endgroup$
1
$\begingroup$

No it does not work that way. For example $11$ is a prime, and $13$ is a prime. $11\times13=143$ is not a prime, but can neither be devided by $2,5,7,9$, or any other number which isn't $11$ or $13$.

$\endgroup$
1
$\begingroup$

The general rule is, you need to check all the primes up to the square root of the number in question. So, for 2 digit numbers, you only need to check the primes less than 10 (2,3,5,7). Once you pass 121 though, you need to start checking 11, once you pass 169, you need to start checking 13, etc.

$\endgroup$
1
$\begingroup$

No, any products of two or more primes $11$ or larger fit this description;the first few examples are already in the three-digit range: $121, 143, 165, 169 \ldots$. So, your criterion works for numbers $\leq 120$ but fails for larger numbers. In general, to check whether a number $n$ is prime, you only need check whether $n$ is divisible by the primes $p \leq \lfloor \sqrt{n} \rfloor$.

$\endgroup$
  • $\begingroup$ I'm sorry, i meant is there any number above a single digit that cannot be divided by a single digit WITHOUT it being a prime number? $\endgroup$ – Iain Blackwood Sep 26 '14 at 15:11
  • $\begingroup$ I edited the answer to avoid the obvious garbling. $\endgroup$ – Travis Sep 26 '14 at 15:32
0
$\begingroup$

Do you mean for $33$ or $121$ to be counted as prime numbers?


Note that the Sieve of Eratosthenes works by successively eliminating multiples of $2,3,5,7,11 \dots$

Once you have got to the prime $p$ you can be sure that any number left which is less than $p^2$ is prime.

Your list fails in two respects. First it is a finite list, but there are infinitely many primes (a fact known to Euclid). Take a prime not on your list, say $11$, and its square will not be prime.

Secondly you have chosen $9$, which is not prime. This doesn't make a huge difference here, because a number is either a power of $3$, in which case it is eliminated (except for $1,3$), or it has a prime factor other than $3$, in which case it would be eliminated by that prime (hence my example of $33$).

There would be a real problem, though, if you tried to work with squares of all the primes - say $9, 25$ when you would be counting $15$ as a prime.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.