Loops Practice 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 Program to input a number from user and find all factors of the given number using for loop.
Input
num = 12Output
Factors of 12: 1, 2, 3, 4, 6, 12Intuition
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 in all Languages
C++ Code
#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;
}Java Code
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int num;
// Input number from user
// Enter any number to find its factors
num = scanner.nextInt();
System.out.print("All factors of " + num + " are: ");
// 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) {
System.out.print(i + ", ");
}
}
scanner.close();
}
}
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 = 17Output
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 = 0indicating 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 in all Languages
C++ Code
#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;
}
Java Code
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int num;
boolean isPrime = true; // Initially assume the number is prime
// Input a number from the user
// Enter any number to check if it's prime
num = scanner.nextInt();
// Check divisibility of num starting from 2 up to num / 2
for (int i = 2; i <= num / 2; i++) {
if (num % i == 0) {
// Set isPrime to false, indicating the number is composite
isPrime = false;
break; // Exit the loop if a divisor is found
}
}
// Check if the number is prime
if (isPrime && num > 1) {
System.out.println(num + " is a prime number.");
} else {
System.out.println(num + " is a composite number.");
}
scanner.close();
}
}
Problem 3
Write a C++ program to print all Prime numbers between 1 to n using loop
Input
end = 20Output
Prime numbers between 1-20: 2, 3, 5, 7, 13, 17, 19Intuition
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 in all Languages
C++ Code
#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;
}
Java Code
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int i, j, end, isPrime;
// Input upper limit to find prime numbers
Scanner scanner = new Scanner(System.in);
//System.out.println("Find prime numbers between 1 to:");
end = scanner.nextInt();
System.out.println("All prime numbers between 1 to " + end + " are:");
// Find all Prime numbers between 1 to end
for (i = 2; i <= end; i++) {
// Assume that the current number is Prime
isPrime = 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) {
isPrime = 0;
break;
}
}
// If the number is prime then print
if (isPrime == 1) {
System.out.print(i + ", ");
}
}
scanner.close();
}
}
Problem 4
Write a C++ program to input a number from user and find Prime factors of the given number using loop.
Input
num = 10Output
Prime factors of 10: 2, 5Intuition
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
numto 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 in all Languages
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;
}
Java Code
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int i, j, num, isPrime;
// Input a number from the user
Scanner scanner = new Scanner(System.in);
//System.out.println("Enter any number to print Prime factors:");
num = scanner.nextInt();
System.out.println("All Prime Factors of " + num + " are:");
// 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
isPrime = 1;
for (j = 2; j <= i / 2; j++) {
if (i % j == 0) {
isPrime = 0;
break;
}
}
// If 'i' is a Prime number and factor of num
if (isPrime == 1) {
System.out.print(i + ", ");
}
}
}
scanner.close();
}
}
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 : )