problem link- PRIME1
my below solution of PRIME1 problem is giving time limit exceed to my code…
can anyone explain time Complexity Analysis of my solution, and what changes should i perform to decrese time limit
any suggestion for solution update required
/*
* 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 PracticeMedium;
import java.util.Scanner;
/**
*
* @author Hemant Dhanuka
*/
class Prime1_1 {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int noOfCases = s.nextInt();
for (int i = 0; i < noOfCases; i++) {
int m = s.nextInt();
int n = s.nextInt();
calculatePrime(m, n);
System.out.println();
}
}
private static void calculatePrime(int m, int n) {
int count = 0;
if (m == 1) {
m = m + 1;
}
for (int i = m; i <= n; i++) {
boolean isPrime = true;
for (int j = 2; j <= Math.sqrt(i); j++) {
if (i % j == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
count++;
}
}
System.out.println(count);
}
}
due to suggestion, i tried to solve PRIME1 with “sieve of Eratoshenes”… but got TLE again
/*
* 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 PracticeMedium;
import java.util.Scanner;
/**
*
* @author Hemant Dhanuka
*/
class Prime1_SieveOfEratosthenes1 {
static int b = 1000000001; //1000000001;
static boolean a[] = new boolean[b];
public static void main(String[] args) {
a[0] = true;
a[1] = true;
Scanner s = new Scanner(System.in);
int noOfCases = s.nextInt();
calculate();
for (int i = 0; i < noOfCases; i++) {
int firstNo = s.nextInt();
int lastNo = s.nextInt();
printPrimeNo(firstNo, lastNo);
System.out.println();
}
}
private static void calculate() {
for (int i = 2; i < Math.sqrt(b); i++) {
if (!a[i]) { //a[i]==false
int p = 2;
for (int j = i; i * p <b ; p++) {
j = i * p;
a[j] = true;
}
}
}
System.out.println("hello");
}
private static void printPrimeNo(int firstNO, int lastNo) {
for (int i = firstNO; i <= lastNo; i++) {
if (!a[i]) {
System.out.println(i);
}
}
}
}
plase explain time analysis of "Sieve of Eratosthenes
" solution… and why its giving TLE error…
If difference between m and n is worst case, i.e. 10^5, and lets say m=10^9 - 10^5 and n= 10^9 then-
for (int i = m; i <= n; i++) //will run 10^5 times.
{
boolean isPrime = true;
for (int j = 2; j <= Math.sqrt(i); j++)//will run root(10^9) ~3.2 x 10^4 times
`` {
if (i % j == 0) {
isPrime = false;
break;
}
}
No of operations are ~3.2 x 10^ 9 [for single test case. For 10 test cases, multiply again with 10, making it ~3.2 x 10^10], so I expect it to give tle. If I recount correctly, we could perform somewhere ~10^8 operations per second for online judges.
The complexity is of order 2 due to nested loops. Need help regarding time optimisation, or you wish to give it another shot yourself? 
EDIT- As a thumb rule, if inputs are somewhere around 10^5, then a crude O(N^2) is expected to give TLE. However, I have seen exceptions too where good optimisation makes the code pass (although barely. Eg- Time limit 1sec, code passes at 0.9990 )
3 Likes
int P_G(long n)
{
if(n==1)
return 0;
if(n==2)
return 1;
if(n%2==0)
return 0;
for(long i=3;i<=sqrt(n);i+=2)
{
if(n%i==0)
return 0;
}
return 1;
}
That is my function in C. the only difference lies in your calculate prime function.
If a number is even, then you can directly say that it’s not prime. No need to loop for that.
Also please check the loop which you used with that of mine. It can be further optimised.
1 Like
Yes. This is a good way to solve it.
1 Like
Still, if you are using java, then I am not very confident that even this solution will pass (Although it worked with C++), I guess it will give TLE. 
It works in JAVA too! Just tried
If your algo is correct, then language shouldn’t be an issue, atleast not on sites like codechef and hackerrank. Good job buddy
Sometimes fast IO also plays role, that’s why I wasn’t sure!!
1 Like
In order to solve this problem more efficiently you can read about segmented sieve of eratosthenes and then solve this problem.
@naksh9619 i tried it “sieve of eratosthenes” but getting TLE again? plz explain why
/*
* 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 PracticeMedium;
import java.util.Scanner;
/**
*
* @author Hemant Dhanuka
*/
class Prime1_SieveOfEratosthenes1 {
static int b = 1000000001; //1000000001;
static boolean a[] = new boolean[b];
public static void main(String[] args) {
a[0] = true;
a[1] = true;
Scanner s = new Scanner(System.in);
int noOfCases = s.nextInt();
calculate();
for (int i = 0; i < noOfCases; i++) {
int firstNo = s.nextInt();
int lastNo = s.nextInt();
printPrimeNo(firstNo, lastNo);
System.out.println();
}
}
private static void calculate() {
for (int i = 2; i < Math.sqrt(b); i++) {
if (!a[i]) { //a[i]==false
int p = 2;
for (int j = i; i * p <b ; p++) {
j = i * p;
a[j] = true;
}
}
}
System.out.println("hello");
}
private static void printPrimeNo(int firstNO, int lastNo) {
for (int i = firstNO; i <= lastNo; i++) {
if (!a[i]) {
System.out.println(i);
}
}
}
}
@hemant_dhanuka
Leave TLE aside, how are you able to declare an array of size ~10^9 in first place? Why aren’t you getting some memory error?
Regarding your doubt, The sieve is kind on O(N^2) with optimisations. But problem is that the online judge performs only ~10^8-10^9 instructions a second, so even a O(N) algo would fail here.
I think you misunderstood what naksh when he said "segmented sieve of eratosthenes "
Check explanation and code of segmented sieve here . The most important part of code there is-
int limit = floor(sqrt(n))+1;
i.e. simple sieve only till sqrt(n)+1, instead of whole n.
@hemant_dhanuka first of all I have written segmented sieve of eratosthenes and you are using sieve of eratosthenes.The range of a and b in PRIME1 problem are large so you cannot simply declare an array of size 10^9 as this will not fit into memory.
This is where segmented sieve helps us.The idea of segmented sieve is to divide the range [0…n-1] in different segments and compute primes in all segments one by one.You can read it from the link provided by @vijju123 and then implement the same.
@vijju123
static int b = 1000000001;
static boolean a[] = new boolean[b];
1000000001* 1 bytes
= 976562 KB
= 953.67 MB
= .93GB
and i think in this memory may be this much memory is available in heap… that’s why i am able to allocate this much memory dynamically
@naksh9619 u are suggesting me “segmented sieve of eratosthenes” over “sieve of eratosthenes” because that much continuous memory is not available… any more difference other than this…
Ok. Possibly for some cases. But the downside is that iterating over 10^9 elements require similar no. of operations. And this will surely give you a tle. Thats why naksh suggested segmented sieve. Go through my link, all this is discussed there
@vijju123 u were right dear… program running on my compiler but not on codechef compiler… here heapmemory finished
It gave me error too, that heap memory got exhausted. Haha, np bro, sometimes even the best of us make mistakes
Not only memory this will help you to decrease time limit too.
1 Like
@hemant_dhanuka , you can read about segmented sieve here and try to code the same by yourself.