1 / 1
Aug 2010

Hi I am new to spoj. Im used to programming in my college but not at this level. I've answered to some problems but the problem is I get TLE error most of the times. I can understand that spoj will have large test cases to check the validity of the program. I have solved the Prime1 problem and I get again the same TLE error. If someone can help me with it it would be great. Thanks a lot in advance.

import java.io.*;
public class prime
{
	static int[] primes=new int[1230];
	public static int binary_search(int start,int end,int r)
	{
		int mid=(start+end)/2;
		if(primes[mid]==r)
		return 1;
		if(end<start)
		return 0;
		if(r<primes[mid])
		 return binary_search(start,mid-1,r);
		else
		 return binary_search(mid+1,end,r);
	}
	public static int isprime(int q,int r)
	{
		int k,i,remainder;
		boolean prime=true;
		if(q==0&&r==2)
			return 1;
		if(r%2==0)
			return 0;
		else
		if(q==0)
		{
			k=binary_search(0,1229,r);
			if(k==1)
				return 1;
			else
				return 0;
		}
		else
		{
			for(i=1;i<1229;i++)
			{
				remainder=((q*(10000%primes[i]))%primes[i]+(r%primes[i]))%primes[i];
				if(remainder==0)
					return 0;
			}
		}
		return 1;
	}
	public static void go()
	{
		int i=3;
		boolean check=true;
		primes[0]=2;
		int num=1,l,j;
		boolean prime;
		while(check)
		{
			prime=true;
			for(j=0;j<num;j++)
			{
				l=i%primes[j];
				if(l==0)
					{
					prime=false;
					break;		
					}
			}
			if(prime==true)
			{
				primes[num]=i;
				num++;
			}
			i=i+2;
			if(i>10000)
				check=false;
		}
	}
	public static int[] convert(String s)
	{
		int remainder,i,q;
		int length=s.length();
		int[] result=new int[2];
		if(length<5)
		{
			result[0]=0;
			result[1]=Integer.parseInt(s);
			return result;
		}
		else
		{
		String temp=new String();
		for(i=length-4;i<length;i++)
		{
			temp=temp+s.charAt(i)+"";
		}
		remainder=Integer.parseInt(temp);
		temp="";
		for(i=0;i<length-4;i++)
		{
			temp=temp+s.charAt(i)+"";
		}
		q=Integer.parseInt(temp);
		result[0]=q;
		result[1]=remainder;
		return result;
		}
	}
	public static String reconvert(int a,int b)
	{
		String result;
		if(a==0)
		result=b+"";
		else
		result=a+""+b;
		return result;
	}
	public static void function(String s)
	{
		String[] a=s.split(" ");
		int i,k;boolean check=true;
		String start=a[0];
		String end=a[1];
		int[] result1=new int[2];
		int[] result2=new int[2];
		result1=convert(start);
		result2=convert(end);
		while(check)
		{
			if(result1[0]==result2[0]&&result1[1]==result2[1])
			{
				k=isprime(result1[0],result1[1]);
				if(k==1)
				System.out.println(reconvert(result1[0],result1[1]));
				break;
			}
			else
			{
				k=isprime(result1[0],result1[1]);
				if(k==1)
				System.out.println(reconvert(result1[0],result1[1]));
				result1[1]++;
				if(result1[1]==10000)
				{	
					result1[0]++;
					result1[1]=0;
				}
			}
		}
	}
	public static void main(String[] args) throws Exception
	{
		go();int i=0;
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int num_cases=Integer.parseInt(br.readLine());
		String[] cases=new String[10];
		for(i=0;i<num_cases;i++)
		{
			cases[i]=br.readLine();
		}
		System.out.println();
		for(i=0;i<num_cases;i++)
		{
			function(cases[i]);
			System.out.println();
		}
	}
}

Suggested Topics

Want to read more? Browse other topics in JAVA based languages or view latest topics.