Computers and Mathematics

As some of you may already know,there is a significant relationship between Mathematics and Computer Programming. Many mathematicians use programming to aid in their research. It can be an invaluable tool to achieving success in whatever proof you may be working on. My interest in how they connect is the algorithms you must create to apply to your program. In order to utilize a computer program to aid you in mathematics you must first write an algorithm,assuming you already know the programming language you will be using. The algorithm must then be translated to work in the programming language you chose.

Prime Number Checking

One of the most basic programming solutions is writing a program to find out if a given number is a prime number. The first step is to develop your algorithm. There are many different ways to check the if a number is prime or not. Most of them fairly complex, however there is one very simple technique. A prime number is only evenly divisible by one and itself. So the easiest way is to use modular division, which is simply dividing two numbers and keeping only the remainder. For example 32 modulo 5 = 2,

because 5 goes into 32, 6 times with a remainder of 2. Since prime numbers are only evenly divisible by one and themselves, prime numbers would always have a remainder greater than 0 when divided by all other numbers(other than 1 and themselves). With this knowledge we know that we have to test all numbers between one and the number we want to check if its prime.This can be limited even further by adding that the factors on any number can not exceed the square root of that number. Now our plain language algorithm is :

get number and call it n

calculate square root of n

test all numbers >=2 and <= square root of n

and if none of the numbers tested return a 0 remainder the number is prime

Java code to find if a number is prime

Our next step is to translate our algorithm into computer code. I will use java because that's my favorite so far. If you are not familiar with java you can find out more at http://docs.oracle.com/javase/tutorial/getStarted/index.html

The part of our algorithm where we calculate the square root and test all the numbers up to the square root is best achieved by a for() loop.the variable we will use to represent the number we want to test will be n and we will make it a "double" data type we will be using double for two reasons one the included Math.sqrt method we will be calling requires a double,.and the second reason is that we can check much higher numbers with double.The next variable we want will be used to store the numbers we are using in our modular division we will call it k and make it a double

lets code out our for() loop

```
double n;
```

double k;

for(double k = 2;i<=Math.sqrt(n);k++){

if(n%k == 0){

return false;

}

} return true;

That is our complete algorithm for prime checking translated into Java. I have tested this algorithm for numbers up to 500 digits long before it started to slow my pc. which is a few years old. I will gladly answer any question or comments on how to implement this into your java project as well as put more posts with how to make other java programs related to mathematics. Just leave a comment with you questions, requests, or suggestions . Thank you for stopping by.

Thank you for your comment. I will be adding more posts relating mathematics and computer science soon. I have been so busy lately taking multiple courses at the same time.

ReplyDeleteI just wanted to add there is a typo in the code above.

ReplyDeleteThis line

for(double k = 2;i<=Math.sqrt(n);k++)

needs to be

for(double k = 2;k<=Math.sqrt(n);k++)