Pagain tle

[dursalakihoegalo]

Please help! How to avoid TLE?

import random
from bisect import bisect_left
import sys
import psyco
psyco.full()
def modulo(a, b, c):
    x = 1
    y = a
    while b>0:
        if b&1:
            x = (x*y)%c
        y = (y*y)%c
        b/=2
    return x%c
def Miller(p, iteration):
    if p<2: return False
    if p!=2 and not p&1:
        return False
    s = p-1
    while not s&1:
        s/=2
    for i in range(iteration):
        a = random.randint(1, p-1)
        temp = s
        mod = modulo(a, temp, p)
        while temp!=p-1 and mod!=1 and mod!=p-1:
            mod = (mod*mod)%p
            temp*=2
        if mod!=p-1 and not temp&1:
            return False
    return True
def primes2(n):
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    if n==3:
        return len([2])
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1,int(n**0.5)//3+1):
      if sieve[i]:
        k=3*i+1|1
        sieve[      k*k//3      ::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
        sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]
def solve():
    primes =  primes2(65536)
    s = sys.stdin
    t = int(s.readline())
    for i in s:
        n = int(i)
        n-=1
        if n<65536:
            ind = bisect_left(primes, n)
            if primes[ind] >= n: ind-=1
            print  primes[ind]
        elif n > 4294967291:
            print 4294967291
        else:
            while True:
                test = Miller(n, 3)
                if test:
                    break
                else:
                    n-=2
            print n
if __name__ == '__main__':
    solve()

[numerix]

Try this one:

1
1234567898

[dursalakihoegalo]

I get

1234567891

[francky]

The main problem is the time !
(And your is_prime function is not deterministic, so it can fail ...)

Why is there so few Python AC ?
It's a hard problem in Python.

You have to write a much better program for that.
You should try other problems before this one in Python.

[dursalakihoegalo]

@francky - thanx for the reply. I wrote a C++ solution also, but failed in that too. I tried many tips from the forum but failed. Hope to solve this one someday. Any suggestion to improve my code would be helpful.
Thank you.

[numerix]

[quote="dursalakihoegalo"]I get

1234567891

[/quote]

Sorry, my mistake. Another one:

1
223223

But, indeed, as francky pointed out, it's not a single screw that has to be adjusted in your code to get AC.
The code must be well optimized to get AC even with psyco and it has to be VEEERY WELL optimized to get a Python 3.1 solution AC (without psyco).
That's not an easy thing.

[vikas_pandey_sof]

hey...plz help me with this problem....m geting tle....i have used miller-rabbin....thanks in advance..

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
typedef unsigned long long int int64;
using namespace std;
int64 mulmod(int64 a,int64 b,int64 c);
int64 modulo(int64 a ,int64 pow,int64 n)
{
	int64 y,u;
	y=1;
	u=a;
	//cout<<"y"<<" "<<"u"<<" "<<"pow"<<"\n";
	while(pow > 0)
	{
		//cout<<y<<" "<<u<<" "<<pow<<"\n";
		if(pow%2 == 1)
			y=mulmod(y,u,n);
		u = mulmod(u,u,n);
		pow/=2;
	}
	return y%n;
}
int64 mulmod(int64 a,int64 b,int64 c)
{
	int64 x=0,y=a%c;
	while(b>0)
	{
		if(b%2==1)
		{
			x = (x+y)%c;
		}
		y = (y*2)%c;
		b/=2;
	}
	return x%c;
}
bool miller(int n,int it)
{
	if(n<2)
		return false;
	if(n!=2 and n%2==0)
		return false;
	int s=n-1;
	while(s%2==0)
		s/=2;
	for(int i=0;i<it;i++)
	{
		int64 a = rand()%(n-1)+1,temp=s;
		int64 mod = modulo(a,temp,n);
		while(temp!=n-1 && mod!=1 && mod!=n-1)
		{
			mod = mulmod(mod,mod,n);
			temp*=2;
		}
		if(mod!=n-1 and temp%2==0)
		{
			return false;
		}
	}
	return true;
}
int main()
{
	int n;
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		n--;
		if(n!=2 and n%2==0)
			n--;
		while(!miller(n,5))
			n-=2;
		printf("%d\n",n);
	}
	return 0;
}