Can you tell me the approach to solve the Not So Easy Problem?

#1

I’m not able to figure out the optimized solution!

#2

you need to find out number of numbers not divisible by prime numbers between 1 to 20.
there is a very classical question of finding all the prime numbers in a given range. I will tell you the solution of this very classical problem and your job is to figure out how can you leverage this solution to get your own.

In questions that demand prime numbers within certain range, we use a method named as
“Sieve of Eratosthenes”, as naive methods has much more time complexity.

Sieve of Eratosthenes is a simple and ancient algorithm used to find the prime numbers up to any given limit. It is one of the most efficient ways to find small prime numbers. For a given upper limit n the algorithm works by iteratively marking the multiples of primes as composite, starting from 2.
How this works?
say n = 20
step1. we have an array from 2 to 20 --> 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
step2. we will be cancelling out numbers one by one which can’t be a prime number.
starting from first number i.e. 2. we remove all multiples of 2 present in this array except 2.
so array now–> 2 3 5 7 9 11 13 15 17 19
step3. next number is 3. remove all multiples of 3 except 3.
array now --> 2 3 5 7 11 13 17 19
step4. remove multiples of 5 except 5. then 7 . then 11… so on.
…
you will see the final list is 2 3 5 7 11 13 17 19.

now we need to implement this algorithm in an efficient way. one such nice implementation is:

this code takes n as no of test cases. then for each test case it prints no of primes between a range [a,b]

import java.util.*;

public class temp {
public static void main(String args[]) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int arr[] = new int[1000005];
// System.out.print(arr[0]);
primeSieve(arr);
while (n-- > 0) {
int count = 0;
int a = cin.nextInt(), b = cin.nextInt();
for (int i = a; i <= b; i++) {
if (arr[i] == 1) {
count++;
}
}
System.out.println(count);
}
}
public static void primeSieve(int[] prime) {
for(int i=2;i<prime.length;i++)
prime[i] = 1;
for(int p = 2; pp <prime.length; p++)
{
// If prime[p] is not changed, then it is a prime
if(prime[p] == 1)
{
// Update all multiples of p
for(int i = pp; i < prime.length; i += p)
prime[i] = 0;
}
}
}
}

Now you need a change this code a little bit to fit into this problem.

Thanks.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.