How do you identify prime numbers?

Question

Gianna Caruso · Accepted Answer

Please see below.

I understand we are trying to identify larger primes, say at least more than #20#. Further, let us try to divide the number only with prime numbers, as in case they are divisible by a composite number, they will be divisible by its prime factors too. One of simplest thing that comes to one, who is trying to identify prime numbers, is that a prime number does not have in unit's digit #{0,2,4,5,6,8}#, as the number will then will be divisible by #2# and #5#. Also sum of all the digits should not be divisible by #3#. These too themselves will remove a large number of composites. Another important thing is that one need not try all the primes (other than #{2,3,5}#, which we have already eliminated). If the number is #n# and the prime number just below its square root is #m#, then we should try only till #m#. The reason is that if a prime number up to less than #m# does not divide #n#, then no other than prime will divide it. As if #n# has a factor greater than #m#, say it is #x# and other factor is #y# i.e. #x*y=n#, then #y=n/x

Noah Archer · Answer

undefined A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. To identify prime numbers, you can follow these steps:

1. Start with the number you want to check.
2. Determine if the number is greater than 1. Prime numbers are always greater than 1.
3. Check if the number is divisible by any integer other than 1 and itself. If it is, then it's not a prime number. If it's not divisible by any other integer, then it's a prime number.

One way to check for divisibility is to divide the number by each integer from 2 up to the square root of the number. If none of these divisions result in an integer quotient, then the number is prime.

For example, to check if 17 is prime:
- Start with 17.
- Check if it's greater than 1 (which it is).
- Test divisibility by dividing 17 by integers from 2 up to the square root of 17 (which is approximately 4.12). You would divide 17 by 2, 3, and 4. None of these divisions result in an integer quotient, so 17 is prime.

This method of checking divisibility works efficiently for smaller numbers. For larger numbers, more sophisticated algorithms, such as the Sieve of Eratosthenes or probabilistic primality tests, may be used.