Timelimit error in this question:print nth prime no

#1

package com.company;

import java.util.Scanner;

public class problem {
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
int n=s.nextInt();
int p;
for(int row=1;row<=n;row++){
p=s.nextInt();
int g=0;

        int k=1;
        while(g!=p){
            k++;
            int count=0;
            for(int j=1;j<=k;j++)
                if(k%j==0)
                    count ++;
                if(count==2){
                    g++;
                }

        }
        System.out.println(k);
    }
}

}

#2

The code would give time limit exceeded error as the time complexity is very high because you are calculating prime each time again and again.
Instead a better and more optimized approach is to pre-compute an array of prime numbers and the simply look up the Nth element of the array for each test case.

1 Like