It looks like you're trying to calculate everything on-place for each execution, which can be quite time-consuming. Try to input "2 5000000" and see if it takes a considerable amount of time (one that you can notice when running the program). If it does, then the TLE is due to this fact, and you should try another approach, such as precalculating values for some specific intervals...
EDIT: I compiled your program and it is much too slow for the 3 seconds you're given... try "2 100000" and see how long it takes!
There a few problems with the code. I can definitely tell that it is TLE even without running the code.
First factor(n) is too slow for 3 secs. Why not use the information in the sieve to help you factor? If you coded it correctly, factoring n can be done using O(k) operations for each n, where k is the number of prime factors of n.
Second, trying to sum all of the factors every time you compute an answer is also too slow. You need to use a culminative sum to allow you to answer the query in O(1) time.
import java.io.*;
import java.util.*;
public class Main
{
static final int Max = 5000000;
static boolean Final[] = new boolean[Max+1];
static boolean Vec[] = new boolean[Max+1];
static int Pri[] = new int[348513];
static Hashtable<Integer,Integer> Hash;
static void Sieve(int L, int U)
{
for (int i=L;i*i<=U;i++)
if (!Vec[i])
for (int j=i+i;j<=U;j+=i)
Vec[j] = true;
return;
}
static boolean Proceso(int Num)
{
if (Num == 1) return false;
if (!Vec[Num]) return true;
Hash = new Hashtable<Integer,Integer>();
int Count = 0;
while (Num % 2 == 0)
{
if (Hash.get(2) == null)
{
Hash.put(2,0);
Count += 2;
}
Num /= 2;
}
if (Num == 1) return true;
int Pos = 1;
while((Pri[Pos]*Pri[Pos]) <= Num)
{
if (Num % Pri[Pos] == 0)
{
if (Hash.get(Pri[Pos]) == null)
{
Hash.put(Pri[Pos],0);
Count += Pri[Pos];
}
Num /= Pri[Pos];
}
else
Pos++;
}
if (Num != 1 && Hash.get(Num) == null)
{
Hash.put(Num,0);
Count += Num;
}
return !Vec[Count];
}
static void Load() //Load Only Primes[2,3,5,7,9]
{
int Pos = 0;
for (int i=2;i<=Max;i++) if (!Vec[i]) Pri[Pos++] = i;
return;
}
static void Load_Final()//Load True Is The Sum Of Factors Of x is A Prime.....
{
for (int i=2;i<=Max;i++) Final[i] = Proceso(i);
return;
}
public static void main(String[] args) throws Exception
{
//BufferedReader In = new BufferedReader(new InputStreamReader (System.in));
BufferedReader In = new BufferedReader(new FileReader (new File ("In.txt")));
long xx = System.nanoTime();
Sieve(2,Max);
Load();
Load_Final();
System.out.println("Cargando "+(System.nanoTime()-xx)/1000000+"ms.");
StringBuffer MiSol = new StringBuffer();
while (true)
{
StringTokenizer x = new StringTokenizer(In.readLine());
if (x.countTokens() == 1) break;
int a = Integer.parseInt(x.nextToken());
int b = Integer.parseInt(x.nextToken());
if (a > b)
{
int Aux = a; a = b; b = Aux;
}
int Sol = 0;
for (int i=a;i<=b;i++) if (Final[i]) Sol++;
MiSol.append(Sol).append('\n');
}
System.out.print(MiSol);
System.out.println((System.nanoTime()-xx)/1000000+"ms.");
}
}
I computed primes using sieves and then used these to evaluate whether an number is Deprime or not and I checked and stored this Deprime condition for every number ,prior to taking input ,but it gives me TLE please help me out!!
I get ACC with 1.5 s. My basic idea is to have a sieve like approach and then answering query in O(1). There are some very fast solutions to this problem. Any one care to share the idea ? thanks.
I am getting TLE. please help me.
I used sieve method to store all the prime between the range. then find the dePrime and store. I use cumulative array to store
all the sum. but i am getting TLE.
Why??????????
My code is given below
long Sum(long n, long a[]) /* a[] stores primes from 2 to 2221 */
{
long r = 0, i = 0;
while(n > 1)
{
if(isPrime(n,a))
{
r += n;
break;
}
while(n%a[i])
i++;
while(n%a[i] == 0)
n /= a[i];
r += a[i];
}
return r;
}
