# 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 like`for(i=2; i<=num/2; i++)`

. - 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. - 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 of`num`

. The loop structure should look like`for(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 : )