Prime Generator Problem. Code working on laptop but not on CodeChef!!!!

general
,
1

import java.util.Scanner;

public class Main {

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    int t2 = 2*t;
    
    
    Scanner sc2 = new Scanner(System.in);
    int[] array = new int[t2];
    for(int i=0;i<t2;i = i+2) {
        array[i] = sc2.nextInt();
        array[(i+1)] = sc2.nextInt();
        
    }
    
    
    for(int i=0;i<t2;i = i+2) {
        for(int k = array[i];k <= array[(i+1)];k++) {
        if(PrimeCheck(k) == true) {
            System.out.println(k);
        }
        
        
    }
        System.out.println("");
    }
    
}

public static boolean PrimeCheck(int n) {
    boolean output = true;
    
    if(n==1) {
        output = false;
    }
    
    else {
        for(int i = 2;i<=n/2;i++) {
        if(n%i == 0) {
            output = false;
        }
    }
    }
    
    return output;
}

}

2

I tried the same code on ideone. It gave me RTE (link1).

I removed second Scanner object(sc2) and used first(sc) to take in values of array and it worked fine (link2).

1 Like
3

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.Arrays;

public class Main {

public static void main(String[] args) throws IOException {
    
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

int t = Integer.parseInt(in.readLine());
int t2 = 2*t;


int[] array = new int[t2];
for(int i=0;i<t2;i = i+2) {
    
   String[] s = in.readLine().split(" ");
   array[i] = Integer.parseInt(s[0]);
   array[(i+1)] = Integer.parseInt(s[1]); 
    
}


for(int i=0;i<t2;i = i+2) {
    PrimeSieve(array[i],array[i+1]);
    if(i!=t2 - 2) {
        System.out.println("");
    }
    
}

}

public static void PrimeSieve (int n,int N) {

    // initially assume all integers are prime
    boolean[] array = new boolean[N + 1];
    array[1] = false;
    
    for (int i = 2; i <= N; i++) {
        array[i] = true;
    }

    // mark non-primes <= N using Sieve of Eratosthenes
    for (int i = 2; i*i <= N; i++) {

        // if i is prime, then mark multiples of i as nonprime
        // suffices to consider mutiples i, i+1, ..., N/i
        if (array[i]) {
            for (int j = i; i*j <= N; j++) {
                array[i*j] = false;
            }
        }
    }

    // print primes
    for (int i = n; i <= N; i++) {
        if (array[i] == true) {
            System.out.println(i);
        }
    }

}
}

4

Hi. Thanks for the advice. The code finally worked but now I have a new problem. The time limit exceeded this time

5

This problem is meant for that :slight_smile: . After all it is a medium level problem. You are using a naive approach. Try to think of a better way in PrimeCheck.
Happy Coding :slight_smile:

6

All right. I got it. Thanks :slight_smile:

7

Hi. I used sieve of eratosthenes to reduce time. Otherwise it’s working perfectly fine but there is again some run time error that I am not able to figure out. Could you help me?
Is there a general error or it’s not working with some special case?