Tle ans wrong answer in 4 test cases

#1

I used segmented sieve but it is giving me TLE as well as wrong answer in some cases

#2

i got a test case where your code is giving wa you can try again and for tle please remove bigintegers and try using only long. If u still get tle provide me the link of the code in which long is used instead of biginteger.

  • for input 1 7 7 your code d’nt print anything.
#3

Getting TLE for second test case.
/*

  • To change this license header, choose License Headers in Project Properties.
  • To change this template file, choose Tools | Templates
  • and open the template in the editor.
    /
    package NumberTheory;
    /    *
  • @author Archit
    /
    import java.math.    ;
    import java.util.;
    public class SegmentedPrimeSieve {
    static boolean[] second;
    static boolean[] first;
    static long a;
    static long b;
    public static void sieve(){
    int n = first.length;
    Arrays.fill(first, true);
    first[0]=false;
    first[1]=false;
    for(int i = 4;i<n;i+=2)first[i]=false;
    for(int i = 3;i<n;i+=2){
    for(int j = i    i;j>0 && j<Integer.MAX_VALUE && j<n;j+=2i){
    first[j]=false;
    }
    }
    }
    public static void cal(){
    Arrays.fill(second, true);
    for(int i= 2;i    i<=b;i++){
    for(int j = 0;j<second.length;j++){
    if(first[i]){
    if(i==j+a) continue;
    if((j+a)%i==0){
    second[j]=false;
    }
    }
    }
    }
    }
    public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    first = new boolean[1000000];
    sieve();
    int t = sc.nextInt();
    for(int tt =0 ;tt<t;tt++){
    a = sc.nextLong();
    b = sc.nextLong();
    int n = (int)(b-a+1);
    second = new boolean[n+1];
    cal();
    for(int i =0;i<n;i++){
    if(second[i] && (i+a)!=1){
    System.out.println(i+a);
    }
    }
    System.out.println();
    }
    }
    }
#4
1 Like
#5

please dont paste your code in comment section provide link for your sol in coding block ide…many syntax error rises if you directly paste your code in comment section as a text.

#6

1st try to optimize time complexity of your cal fun. because your are using almost 10^12 iteration using two nested loops. if you are unable to think how to optimize further i will help u after that.

#7

I am so sorry for adding code to comments but I am not able to optimize my function.

#8

you can just iterate over the multiple of prime in l to r instead of going on one by one in l to r.
just as you do in normal seive. and one more thing no need to go inside the second loop if number is not prime. Are you getting what i am saying ?

#9

Not I am getting wrong answers in same test cases.

#10

Your code is correct and i tested your code with test cases in which it was showing wa in ide. There is something wrong with the checker. I will let you know.

#11

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.

#12

I am still getting wrong ans. for test cases.

#13

i told you your code is correct there is problem with checker i checked your code output for the test cases its same. you can solve another questions. If you want test cases for WA i will provide you that.

1 Like
#14

Okay thanks for the help.