Prateek loves candy problem

#1

while submittimg the code the it says …your submission not judged …but the output is correct
the link of the code is here…“https://ide.codingblocks.com/s/194007”

#2

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

what is the variable pp used in the for loop

#4

its actually p multiply p… multiply operator does not show here.

#5

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.