How do I determine if a number is prime?

Answer 1

How to determine if N is prime....

step 1: Let x = N/2 + 1

step 2: for i=2,3,4,5,.... x

if N / i has no remainder

then N is not prime, as you have found a divisor

step 3: if none of i=2,3,4,5,...x evenly divides N, then it

has no divisors, so it is prime

You can RULE OUT Entire classes of numbers like evens or multiples of 3.

For example, if the N is odd, then you can skip over the even numbers in step 2,

because an odd cannot be divided by even.

another rule for divisibility by 3, is to add the digits.

EX. 123 --> total of the digits is 1+2+3 = 6 , which is a multiple of 3; so 123 divides by 3;

101010102 ---> total of the digits is 6, so again 101010102 divides by 3;

11111111 ---> total of the digits is 8, so it does NOT divide by 3.

Applying this test to N, determines if you must test multiples of 3, or can skip them.

For divisibility by 5, the number N must have zer0 or five as its last digit.

Answer 2

You have asked a VERY BIG question! I will only start you off...because if you really want to get into it you are going to have to study a lot of mathematics. Just so you know: prime numbers are critical to encrypting communications and there is big money in finding the next prime number which will have several hundred (yes, hundred) digits!

There are three things to know at a basic level.

First is the sieve of Eratosthenes. You should look this up in a textbook on college algebra or online. Basically, make a table of all the numbers up to, say 100.

Start with 2 and strike out of your table all the numbers which are multiples of 2.

Then strike out all the numbers which are multiples of 3, then 5, and 7.

Now all the numbers that are left in your table are primes less than 100.

You can start with a table as large as you want (as large as you are willing to complete); you need to strike out the multiples of all the primes up to the square root of the biggest number in your table.

This method was described by the Greeks thousands of years ago and is still the easiest to describe.

Second if you have a specific number which you would like to investigate. The only simple way to find out if it is prime is to start dividing it by successive primes...if you get to the last prime less that the square root of the number in which you are interested, then that number is prime. It is a slow process if the number is quite large.

Third: there are other sieves which boost your efficiency at the cost of some complexity. These are especially useful if you have at least a calculator and preferably a computer. You should go online and look up prime number sieves if you are additionally interested.