MHB 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 .

 

[jedishrfu]

Great summary! There are several other ways of determining if a given number is prime in addition to your method.

This article from Geeks for Geeks implements some algorithms in C++, Java, Python, C#, PHP, and Javascript because sometimes when you're developing an application you need to do this.

https://www.geeksforgeeks.org/prime-numbers/

and this article from Wikihow brings in several other schemes including Fermat's Little Theorem and Miller-Rabin test which dramatically speeds up the testing process but have pitfalls in identifying a number as prime when it is not aka false positive.

https://www.wikihow.com/Check-if-a-Number-Is-Prime