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
- Input number from user. Store it in some variable say num.
- Run a loop from 1 to num, increment 1 in each iteration. The loop structure should look like
for(i=1; i<=num; i++)
. - 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.
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
- Input a number from user. Store it in some variable say
num
. - 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. - Run a loop from 2 to
num/2
, increment 1 in each iteration. The loop structure should be likefor(i=2; i<=num/2; i++)
. - Check, divisibility of the number i.e.
if(num%i == 0)
then, the number is not prime.Setis_prime = 0
indicating number is not prime and terminate from loop. - 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.
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
- Input the upper limit to print prime numbers from the user. Store it in some variable say end.
- Run a loop from 2 to end, increment 1 in each iteration. The loop structure should be like
for(i=2; i<=end; i++)
. - Inside the loop for each iteration print the value of i if it is a prime number.
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
- Input a number from user. Store it in some variable say num.
- Run a loop from 2 to
num
to find factors & potential prime factors ofnum
. The loop structure should look likefor(i=2; i<=num; i++)
. - 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.
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 : )