TLE exception. Can someone optimise the code for problem prateek loves candy

#1

import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t–>0) {
int n = sc.nextInt();
int sum=0;
int i=2;
boolean flag=true;
while(true) {
if(n==0)
break;
for(int j=2;j<=i/2;j++) {
if(i%j==0) {
flag = false;
break;
}
}
if(flag) {
sum=i;
i++;
n–;
}
}
System.out.println(sum);
}
}
}

#2

Hey,
in this question you basically have to print the nth prime number like if input is 5 so the fifth prime number is [2,3,5,7,11] is 11 so you will print 11.Similarly when n=1 then the first prime number is 2 then you will print 2.Just try to think again on this question.

1 Like
#3

My approach is something like this. Do tell me if you have a better approach.
In order to print nth prime number, i have to find prime numbers starting from 2 and decrement n whenever a prime is found and then continue finding next prime number. The loop will stop when n becomes zero and print the last stored prime number in my variable called “sum”.

#4

yes your approach is right.
but for optimizing your code you have to use the seive method.

#5

I have implemented that approach and it is giving me a Time limit exceeded error.
I will be obliged if you can optimize it or provide me your code.

#6

you have to use seive method for optimizing your code.

#7


have a look at this.

#8

I looked at the code you provided and after referring to the above code and an article of GeeksforGeeks, i made my own code but i dont know why it is still giving me time limit exceeded array.

import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t–>0) {
int n = sc.nextInt();
boolean arr[] = new boolean[1000000];
for(int i=0;i<arr.length;i++) {
arr[i] = true;
}

        int ans = 0;

        for(int p=2;p*p<1000000;p++) {
            if(n==0)
                break;
            if(arr[p]==true) {
                n--;
                ans=p;
                for(int i=p*p;i<1000000;i+=p) {
                    arr[i] = false;
                }
            }
        }
        System.out.println(ans);
    }
}

}

#9

Hi, take the variables as long and inspite of first storing the numbers in the array for prime check for that particular number which comes that if that number is prime or not and then do the further work.
See this code and try to dry run it

#10

I liked the approach you told and made my own code. For now, the TLE has been resolved but it is giving me wrong answer on submitting the case.

#11

Please have a look at this code

#13

Hi
you don’t have to make array of size max.

#14

prime[max] is to store the prime numbers. If the maximum input is 5 then i have to find 5 prime numbers and store them accordingly in the prime array. Maybe thats why i need to make prime[] of size max. What exactly are you trying to say?

#15

But the indexing in the array will be till 4 so don’t make array of max size only.