Programming Discrete Math Concepts for Beginners/

...

/

Improving an Algorithm

Improving an Algorithm

Learn to optimize an algorithm with programming constructs.

We'll cover the following...

Understanding algorithms from mathematics to computation

Algorithms are one of the main branches of computer science and discrete mathematics. This is why we use concepts and notations from discrete mathematics in computational algorithms. We can map any problem from mathematical form to a computer program with the help of the same algorithm.

Let’s plunge into code to understand how we can map our problems from the mathematical domain to our computational field. Let’s start with prime numbers. We have plenty of ways to implement it. Let’s first look at what a prime number means.

A prime number is a natural number with exactly two discrete natural divisors. For example, 2 is a prime number because it has precisely two divisors—1 and 2. In the same way, 11 is a prime number because there are precisely two divisors—1 and 11.

Based on that concept, we can write our algorithm in natural language this way:

  1. Use any natural number as input.

  2. Count the number of factors.

  3. If the number of factors is equal to two, classify the the number as prime.

  4. If the number is greater than two, classify the number as not prime.

Finding prime numbers by counting factors

Let’s code this algorithm using the Java programming language.

Note: You can run the following code after entering the input value in the box provided below the code.

Press + to interact
import java.util.*; 
import java.math.*; 
//TryingToFindPrime
class Main{
        private static Scanner sc;
        public static void main(String[] args) {
                int numOne, integerOne;
                //Enter any number to Find Factors
                sc = new Scanner(System.in);
                numOne = sc.nextInt();
                System.out.println("Enter a number to find factors: ");
                System.out.println(numOne);
                int controOne = 0;
                for(integerOne = 1; integerOne <= Math.sqrt(numOne); integerOne++)
                {
                        if (numOne % integerOne == 0) {
                                if (numOne / integerOne == integerOne){ 
                                        controOne++;
                                } else {
                                        controOne = controOne + 2;
                                } 
                        }
                }
                if(controOne == 2){
                        System.out.println(numOne + " is prime."); 
                } 
                else {
                        System.out.println(numOne + " is not prime.");
                }
        } 
}

Enter the input below

We can test the program by giving inputs like 49 and 47.

  • Output 1:
 ...