Prateek loves candy problem

#1

Sir
How do i rectify problem in this:
Scanner obj = new Scanner(System.in);
int t = obj.nextInt();

	if (t <= 10000) {
		int[] arr = new int[100000];
		int k = 0, count = 0;
		arr[count] = 2;

		for (int m = 3; m <= 1000000; m++) {
			for (int j = 2; j < m; j++) {
				k = m % j;
				if (k == 0) {
					break;
				}
			}
			if (k != 0) {
				count += 1;
				arr[count] = m;
			}
		}

		for (int i = 1; i <= t; i++) {
			int n = obj.nextInt();
			System.out.println(arr[n - 1]);
		}
	}
#2

Hi Ekram,
You are exceeding the time limit. The two nested for loops are going till 10^6(approx) and 10^6(approx). Hence, complexity becomes 10^12 (O(n^2)). Avoid that.

#3

Sir i am unable to resolve time limit exceed problem.How do i approach this. And if there is any example where i can understand how to deal with time limit exceed.

#4

Normally we take time limit as 10^7 or 10^8, that is the maximum number of iterations your code has to perform. In this case, you are running 2 nested for loops till 10^6, hence complexity is O(n^2) where n is 10^6 i.e. number of times you are running one loop.
Now, if you’ve to check whether n is a prime number or not, then you needn’t go till n to check if it’s a prime number.

#5

Sir now that i have made an array count[] to include all the primes (upto j here) in it. So what should be the max value of prime required? Also the size of array to store it? Because for less values it is showing run error and for larger values TLE.

#6

Please share your code.

#7

Scanner obj = new Scanner(System.in);
int t = obj.nextInt();

	int[] count = new int[78498];	// there are 78498 primes upto 10^6
			count[0] = 2;

			int rem = 0, x = 1;
			for(int j=3; j<Math.pow(10,6); j++){
				for(int k=2; k<j; k++){
					rem = j%k;
					if(rem==0){
						break;
					}
				}
				if(rem!=0){
					count[x] = j;
					x++;
				}
			}

	if(t<=10000){
		for(int i=0; i<t; i++){
			int n = obj.nextInt();
			System.out.println(count[n-1]);
		}
	}
#8

The main aim of the question is to find the nth prime number. Eg 11 is the 5th prime number (2,3,5,7,11). Now replace the math.pow with 10^6 in numeric terms like 1000000 and use math.sqrt(j) because it will reduce the complexity while calculating primes