Prateek loves candy

#1
  1. the code is running fine on online class but not in ide.
    2)on submission all testcase shows tle.
#2

CodingBlocks IDE is not working properly today , so try to paste in code in some other IDE( like geeksforgeeks) and send me the link.

But if the problem is TLE, the possible reason could be your approach. here is the right approach for such kind of problem.

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
#4

https://ide.codingblocks.com/s/201264 tried the approach but still tile limit error.

#5

here is codepackage cruxonline; import java.util.Scanner; public class PrateekLovesCandy { public static void main(String[] args) { Scanner scn = new Scanner(System.in); int testcase = scn.nextInt(); for (int j = 1; j <= testcase; j++) { int n = scn.nextInt(); int count = 0; int[] arr = new int[1000000]; for (int i = 2; i < arr.length; i++) { arr[i] = 1; } for (int i = 2; i < arr.length; i++) { if (arr[i] == 1) { for (int pp = 2 * i; pp < arr.length; pp += i) { arr[pp] = 0; } } } for (int i = 2; i < arr.length && count<=n; i++) { if (arr[i] == 1) { count++; if (count == n) { System.out.println(i); i=arr.length; } } } } scn.close(); } }

#6

hi, its difficult to analyse a code like this. can you please copy your code into some ide(like geeksforgeeks or tutorialpoints if coding blocks ide is not working) and share the link to me.
Thanks

#7

https://ide.geeksforgeeks.org/iG3cersr3a

#8

hello . already send the link

#9

I made some improvisations on your code. try to understand. if you dont get some point, feel free to ask.

import java.util.Scanner;

public class PrateekLovesCandy {

public static void main(String[] args) {
	Scanner scn = new Scanner(System.in);
	int[] arr = new int[1000000];
	int[] primenos = new int[1000000];
	int k=0;
	for (int i = 2; i < arr.length; i++) {
		arr[i] = 1;
	}
	for (int i = 2; i < arr.length; i++) {
		if (arr[i] == 1) {
		    primenos[k] = i;
		    k++;
			for (int pp = 2 * i; pp < arr.length; pp += i) {
				arr[pp] = 0;
			}
		}
	}
	int testcase = scn.nextInt();
	for (int j = 1; j <= testcase; j++) {
		int n = scn.nextInt();
		System.out.println(primenos[n-1]);
	}
	scn.close();
}

}

thanks