Skip to main content

Control Flow : Practice

Loops 2

Hello coders : )

I hope you have understood the concept and practiced a few problems on loops by now. Now it's time to move to our new set of problems on loops. So buckle up and let's go 🚀

Problem 1

Write a C++ program to input a number from user and find all factors of the given number using for loop. 

Input

num = 12

Output

Factors of 12: 1, 2, 3, 4, 6, 12

Intuition

First of all, what's a factor? Any number which divides the given number is a factor of it.

That means we can simply loop from 1 to the given number say num, and divide it with every no. If the remainder is 0 then the number we divided with is the factor of the given number.

Logic

  1. Input number from user. Store it in some variable say num.
  2. Run a loop from 1 to num, increment 1 in each iteration. The loop structure should look like for(i=1; i<=num; i++).
  3. For each iteration inside loop check current counter loop variable i is a factor of num or not. To check factor we check divisibility of number by performing modulo division i.e. if(num % i == 0) then i is a factor of num.If i is a factor of num then print the value of i.

Try it yourself

Solution 
#include <iostream>
using namespace std;

int main() {
    int num;

    /* Input number from user */
    cout << "Enter any number to find its factor: " << endl;
    cin >> num;

    cout << "All factors of " << num << " are: " << endl;

    /* Iterate from 1 to num */
    for (int i = 1; i <= num; i++) {
        /* 
         * If num is exactly divisible by i
         * Then i is a factor of num
         */
        if (num % i == 0) {
            cout << i << ", ";
        }
    }

    return 0;
}

Problem 2

Write a program in C++ to input a number and check whether the number is prime number or not using for loop.

Input

num = 17

Output

17 is a prime number.

Intuition

Let's have a variable is_prime to do our job i.e. to check if the number is prime or not. It can have 2 values: 0 & 1. If it's 0 then, num is composite & if it's 1 then, num is prime.

Now how to check if a number is prime? Let's first understand what a prime number is. A prime number is a number that doesn't have any factor apart from 1 and the number itself.

Now to check if the given no. num is prime or not, we simply have to check if the num has any factor other than 1 and num or not. Initially assume that the no. is prime and hence is_prime is initialized as 1. Now to perform the check, we can simply run a loop from 2 to num-1 (exclude 1 and num as they cannot be the prime factors a no. num), and divide it with every no. If the remainder is 0 then the number we divided with is the factor of the given number and hence the no. is not prime. In this case, update is_prime as 0 and break from the loop.

Optimization: Do we really need to run a loop till num-1? Let's go back to basic maths. We know that

  • 1 * 8 = 8 * 1 = 8
  • 7 * 4 = 4 * 7 = 28
  • 3 * 5 = 5 * 3 = 15

This implies that if 4 is factor of 28, then, 7 (= 28 / 4) will be also a factor of 28. This is because if a * b = num and a > num/2, then b < num/2.

From the above example, it is clear that I can check only till num/2 (=28/2=14) to find prime factors of it. This will cover all possible divisors and eliminate redundant checks for larger divisors.

PS: We are going to see an even better technique than this later in DSA : )

Logic

  1. Input a number from user. Store it in some variable say num.
  2. Declare and initialize another variable say is_prime = 1. isPrime variable is used as a notification or flag variable. Assigning 0 means number is composite and 1 means prime.
  3. Run a loop from 2 to num/2, increment 1 in each iteration. The loop structure should be like for(i=2; i<=num/2; i++).
  4. Check, divisibility of the number i.e. if(num%i == 0) then, the number is not prime.Set is_prime = 0 indicating number is not prime and terminate from loop.
  5. Outside the loop check the current value of is_prime. According to our assumption if it is equal to 1 then the number is prime otherwise composite.

Try it yourself

Solution 
#include <iostream>
using namespace std;

int main() {
    int i, num, is_prime;

    /*
     * is_prime is used as a flag variable.
     * If is_prime = 0, then the number is composite.
     * If is_prime = 1, then the number is prime.
     * Initially, I have assumed the number as prime.
     */
    is_prime = 1; 

    /* Input a number from the user */
    cout << "Enter any number to check prime: \n ";
    cin >> num;

    for (i = 2; i <= num / 2; i++) {
        /* Check divisibility of num */
        if (num % i == 0) {
            /* Set is_prime to 0 indicating it as a composite number */
            is_prime = 0;

            /* Terminate from loop */
            break;
        }
    }

    /*
     * If is_prime contains 1, then it is prime
     */
    if (is_prime == 1 && num > 1) {
        cout << num << " is prime number";
    } else {
        cout << num << " is composite number";
    }

    return 0;
}

Problem 3

Write a C++ program to print all Prime numbers between 1 to n using loop

Input

end = 20

Output

Prime numbers between 1-20: 2, 3, 5, 7, 13, 17, 19

Intuition

The most simplest approach that comes to my mind here is run a loop from s till num and check if they are prime or not. If they are then we'll print it. We know how to check a prime no. but that also requires a loop right? Hence we'll use a nested loop: Outer loop to iterate over all numbers till end and inner loop to check if no. is prime or not.

Logic

  1. Input the upper limit to print prime numbers from the user. Store it in some variable say end.
  2. Run a loop from 2 to end, increment 1 in each iteration. The loop structure should be like for(i=2; i<=end; i++).
  3. Inside the loop for each iteration print the value of i if it is a prime number.

Try it yourself

Solution 
#include <iostream>
using namespace std;

int main() {
    int i, j, end, is_prime; // is_prime is used as a flag variable

    /* Input upper limit to print prime */
    cout << "Find prime numbers between 1 to: " << endl;
    cin >> end;

    cout << "All prime numbers between 1 to " << end << " are:" << endl;

    /* Find all Prime numbers between 1 to end */
    for (i = 2; i <= end; i++) {
        /* Assume that the current number is Prime */
        is_prime = 1;

        /* Check if the current number i is prime or not */
        for (j = 2; j <= i / 2; j++) {
            /*
             * If i is divisible by any number other than 1 and itself
             * then it is not a prime number
             */
            if (i % j == 0) {
                is_prime = 0;
                break;
            }
        }

        /* If the number is prime then print */
        if (is_prime == 1) {
            cout << i << ", ";
        }
    }

    return 0;
}

Problem 4

Write a C++ program to input a number from user and find Prime factors of the given number using loop.

Input

num = 10

Output

Prime factors of 10: 2, 5

Intuition

This problem is also a combination of 2 problems like the previous one. Here we need one loop to check for factors of the given number num and another loop to check if the given factor. is prime or not. Hence we would run an outer loop on i from 2 to num (1 can't be a prime factor) and check if i is a factor of num or not, i.e. check if (num % i == 0). If it's then we'll run an inner loop from 2 to i/2 so that we can check that if i is a prime factor or just a composite factor. If i is a prime factor then we'll print it in our output. Let's see the step-by-step description now.

Logic

  1. Input a number from user. Store it in some variable say num.
  2. Run a loop from 2 to num to find factors & potential prime factors of num. The loop structure should look like for(i=2; i<=num; i++).
  3. Inside the loop, first check if i is a factor of num or not. If it is a factor then check if it is prime or not. Print the value of i if it is prime and a factor of num.

Try it yourself

Solution 
#include <iostream>
using namespace std;

int main() {
    int i, j, num, is_prime;

    /* Input a number from the user */
    cout << "Enter any number to print Prime factors: "<<endl;
    cin >> num;

    cout << "All Prime Factors of " << num << " are: " << endl;

    /* Find all Prime factors */
    for (i = 2; i <= num; i++) {
        /* Check 'i' for a factor of num */
        if (num % i == 0) {
            /* Check 'i' for Prime */
            is_prime = 1;
            for (j = 2; j <= i / 2; j++) {
                if (i % j == 0) {
                    is_prime = 0;
                    break;
                }
            }

            /* If 'i' is a Prime number and factor of num */
            if (is_prime == 1) {
                cout << i << ", ";
            }
        }
    }

    return 0;
}

Kudos! You did it. We did a lot of questions on loops right but there's a variety of problems that loops have to offer. We'll see more problems in the upcoming article. Till then keep practicing : )