Programming Discrete Math Concepts for Beginners/

...

/

Optimizing the Algorithm

Optimizing the Algorithm

Learn about optimizing the running time of an algorithm.

We'll cover the following...

Ways to decide a prime number

In this lesson, we’ll discuss algorithms and time complexity. First, we’ll look at a few code snippets and the time it takes to run the program. Moreover, we’ll also learn about the underlying logic and algorithm of the code.

By now, we’re familiar with the terms “algorithm” and “time complexity.” We know that our algorithm should be efficient enough to reduce the time to run the code. We should also remember that problems can have many solutions; we just need to find the best algorithm.

Okay, let’s try some code in Dart. In this first case, we’re trying to find the factors of a positive integer. As we know, a positive integer, like 4, has three factorsA factor is an integer that can divide the number. It always starts with 1 and ends with that number.: 1, 2, and 4.

A prime number is a number that can be divided only by 1 and the number itself, such as 2, 3, 5, or 7. The list goes on. It’s easy to find whether a number is prime.

Finding all factors

We can start with a prime number like 5. All we need to do is check whether all the numbers starting from 2 to 4 can divide 5. If any number can divide 5, then 5 is not prime. Otherwise, 5 is prime.

We’ll look at how to do this in a minute. But first, we’ll find the factors of the number 36, which is a composite number (i.e., not prime.) Let’s see what factors 36 has.

Press + to interact
//Dart
import'dart:math';
void main(){
  //we will find factors of 36
  //we can add two factors, 1 and 36 itself
  //time complexity is O(n)
  List<int> numbers= List();
  for(int i=1;i<=36;i++){
    if(36 % i == 0){
      numbers.add(i);
    }
  }
  print("${List.from(numbers)}");
  List<int>moreNumbers= List();
  moreNumbers.add(1);
  for(int i=1;i<=18;i++){
    if(36 % i == 0){
      moreNumbers.add(i);
    }
  }
  moreNumbers.add(36);
  print("${List.from(numbers)}");
  //in both cases below, time complexity is O(square root of n)
  List<double>nums= List();
  for(double j=1; j<=sqrt(36); j++){
    if(36 % j == 0){
      nums.add(j);
      if(j != sqrt(36)){
        nums.add(36/j);
      }
    }
  }
  nums..sort();
  print("${List.from(nums)}");
  List<int>moreNums= List();
  for(int j=1; j<=sqrt(36); j++){
    if(36 % j == 0){
      moreNums.add(j);
      if(j != sqrt(36)){
        moreNums.add((36/j).round());
      }
    }
  }
  moreNums.sort();
  print("${List.from(moreNums)}");
  List<int>numsMore= List();
  for(int j=1; j<=sqrt(35); j++){
    if(35 % j == 0){
      numsMore.add(j);
      if(j != sqrt(35)){
        print("true");
        numsMore.add((35/j).round());
      }
    } 
  }
  numsMore.sort();
  print("${List.from(numsMore)}");
}

Let’s see the output first.

[1, 2, 3, 4, 6, 9, 12, 18, 36]
[1, 2, 3, 4, 6, 9, 12, 18, 36]
[1.0, 2.0, 3.0, 4.0, 6.0, 9.0, 12.0, 18.0, 36.0]
[1, 2, 3, 4, 6, 9, 12, 18, 36]
true
true
[1, 5, 7, 35]

In the code above, we take the number 36 and keep checking all its factors from 1 to itself. If it has a factor, we add it to the numbers list.

  • Lines 16–21: We try the same approach with half of the number 36; we check all the factors of 36 from 1 to 18 and manually add 36 in the end.

  • Line 28: This is followed by a smarter approach where we only check until 36=6 ...