How to find whether a given number is prime or not?

[burgess]

What is a prime number

 

A number is greater than 1 is called a prime number, if it has only two factors, namely 1 and the number itself.

 

Prime numbers up to 100 are:2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

 

Procedure to find out the prime number

 

Suppose A is given number.

 

Step 1: Find a whole number nearly greater than the square root of A. K > square root(A)

Step 2: Test whether A is divisible by any prime number less than K. If yes A is not a prime number. If not, A is prime number.

 

Example:

 

Find out whether 337 is a prime number or not?

 

Step 1: 19 > square root (337)

Prime numbers less than 19 are 2, 3, 5, 7, 11, 13, 17

Step 2: 337 is not divisible by any of them

 

Therefore 337 is a prime number

 

These are simple and easy tricks which are helpful to solve your math homework problems .

[Bignose]

The above is the absolutely slowest method to determine if a number is prime or not: http://en.wikipedia.org/wiki/Primality_test

Edited August 12, 2014 by Bignose

[John Cuthber]

The above is the absolutely slowest method to determine if a number is prime or not: http://en.wikipedia.org/wiki/Primality_test

No, it's not.

There are at least two algorithms that are slower.

Check to see if A is divisible by each integer less than root A in turn.

(This has the marginal advantage that you don't need a list of primes, it is, however stupidly slow)

 

Pick a random integer less than root a and see if that's a factor, if not, pick another random choice.

There is no guarantee that this method will work in any finite time.

[Bignose]

No, it's not.

There are at least two algorithms that are slower.

Check to see if A is divisible by each integer less than root A in turn.

(This has the marginal advantage that you don't need a list of primes, it is, however stupidly slow)

 

Pick a random integer less than root a and see if that's a factor, if not, pick another random choice.

There is no guarantee that this method will work in any finite time.

Well, ok, I cede to the truly terrible prime finding algorithm . We could make it even worse... to check if is prime, divide by n-1, then n-2,... and so on. None of this sqrt(n) jabberwocky.

[jacksen]

Hi,

 

My example to find a prime number or not, if we were to use this method to test whether 11 is prime or not, we would divide 11 by 3, 4, 5, 6, 7, 8, 9, and 10, each time looking for a whole number answer with no remainder. Since none of these numbers divide evenly into 11, we can say that 11 is prime.

[imatfaal]

Hi,

 

My example to find a prime number or not, if we were to use this method to test whether 11 is prime or not, we would divide 11 by 3, 4, 5, 6, 7, 8, 9, and 10, each time looking for a whole number answer with no remainder. Since none of these numbers divide evenly into 11, we can say that 11 is prime.

 

That would be very slow - even slower than the ops. Just for example you don't need to divide by both 8 and 4 - or 9 and 3. The very slow method of the OP is to divide by all primes less than the root of the test - this works but is slow slow slow; yours is worse.

 

Bignose's link gives some quicker ideas

[beejewel]

Some time ago I devised a system of visual numbers, which makes it easy to see prime factors.. I did a page on fb here if you have a fb account you can check it here. https://www.facebook.com/worldofnumbers

[imatfaal]

Some time ago I devised a system of visual numbers, which makes it easy to see prime factors.. I did a page on fb here if you have a fb account you can check it here. https://www.facebook.com/worldofnumbers

 

it's just displaying the prime factors of numbers as dots - doesn't make it any easier. all numbers are either products of prime factors or primes - so you chose to use dots rather than numerical notation; the only difference is that it would become unmanageable with numbers of any size.

 

This thread is number 84981 (you can see it on the url). I represent that with 5 digits. I could show it as 3*13*2179 a few more characters but showing the prime factors - but your system (which has no benefits over my latter representation) would take a lot of paper to show.

[beejewel]

 

 

it's just displaying the prime factors of numbers as dots - doesn't make it any easier.

 

Basically yes, the prime numbers are represented as spheres, with one sphere being the number 2, two spheres being the number 3, three spheres being the number 5 and so on, the shape that forms around the primes is the composite. Think of it like 12 eggs and an egg carton

 

Large groups of spheres can represent complex shapes, think about it and you realise you are such a shape. In fact in my system you (we) are prime numbers.

 

Keep in mind that the human mind is far better at recognising objects than numbers, my 1 year old boy can already recognise many complex objects.

 

Intended more as an aid to teach children about primes, not for finding the prime factors in encryption algoritms.

 

Sterven

 

 

VisualNumbers.pdf

[imatfaal]

Keep in mind that the human mind is far better at recognising objects than numbers, my 1 year old boy can already recognise many complex objects.

I can recognise and understand to almost its entirety any number placed in front of me - even if I haven't seen it before. It is pretty pictures - but I am yet to see any utility