10956  Prime Suspect
Moderator: Board moderators
10956  Prime Suspect
could any one help me please how do i solve i recived wrong answer
 danielrocha
 New poster
 Posts: 44
 Joined: Sun Apr 27, 2003 3:17 am
 Location: Rio Grande do Norte  Brazil
 Contact:
There's one thing I don't understand: if the problemsetter's solution runs in 0:03.197s, don't you think that a time limit of 4s during the contest is a little extreme? I get the impression that we should code exactly like the problemsetter so we can get an AC solution.
And, while in the topic, what kind of optimizations are necessary to pass this problem under 4s? During the contest we used all kinds of crazy bit optimizations, but couldn't get AC. Now we see that it runs in 5.4s.
Our solution is basically to test all odd numbers in the interval and, if they are not prime (we discover this using millerrabin test for bases 2, 7 and 61) and are "suspect" for the given base, we add it to the failures list.
And, while in the topic, what kind of optimizations are necessary to pass this problem under 4s? During the contest we used all kinds of crazy bit optimizations, but couldn't get AC. Now we see that it runs in 5.4s.
Our solution is basically to test all odd numbers in the interval and, if they are not prime (we discover this using millerrabin test for bases 2, 7 and 61) and are "suspect" for the given base, we add it to the failures list.
Daniel
UFRN HDD1
Brasil
UFRN HDD1
Brasil

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
 little joey
 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
The problem itself was fun (thanks little joey!) but I too agree the input was a little too heavy. My program takes 8 seconds (but then again I'm new to this and used cin )
All of you who solved this fast (less than 4 seconds), did you modify the witness algorithm or did you rely on code optimization and fast primality testing?
Thanks.
All of you who solved this fast (less than 4 seconds), did you modify the witness algorithm or did you rely on code optimization and fast primality testing?
Thanks.
10956 sample I/O
Oh, I can't get rid of TLE. If I try to optimize I get WA. I don't know if my program is right at all. Can somone give some I/O?
Thanks in advance.
Thanks in advance.
sieve
For the same problem of time limit exceed, i tried to turn to the sieve algorithm, but the algorithm i know always start the interval that is checking from 2 which is not suitable in both time and memory for that problem.
Any help !!!
Any help !!!
WA in the example
i m not sure if i correctly implemented that suspect function but anyways for the example whose output is:
There are 457 odd nonprime numbers between 4000000000 and 4000001000.
There are no failures in base 2.
I got 500 instead of 457.
here is the suspect function
bool suspect(__int64 , __int64 n)
{
__int64 i,x,lastx,u,t;
for(i=0 ; (n1)>=(((__int64)1)<<i) ; i++)
if((n1)%(((__int64)1)<<i)==0)
t=i;
u=(n1)/(((__int64)1))<<t);
x=(mypow(b%n,u%n)); //mypow is my (log n) power
for(i=1 ; i<=t ; i++)
{
lastx=x;
x = x*x%n;
if(x==1 && lastx!=1 && lastx!=n1)
return false;
}
if(x!=1)
return false;
return true;
}
having 500 as output means that every odd integer in the range gets false from this function.
here is the power function also:
__int64 mypow(__int64 a , __int64 b)
{
__int64 q,r;
if(b==0) return 1;
if(b==1) return a;
q= mypow(a,b/2);
r = b%2==0 ? 1:a;
return (((q*q)%n)*r)%n;
}
There are 457 odd nonprime numbers between 4000000000 and 4000001000.
There are no failures in base 2.
I got 500 instead of 457.
here is the suspect function
bool suspect(__int64 , __int64 n)
{
__int64 i,x,lastx,u,t;
for(i=0 ; (n1)>=(((__int64)1)<<i) ; i++)
if((n1)%(((__int64)1)<<i)==0)
t=i;
u=(n1)/(((__int64)1))<<t);
x=(mypow(b%n,u%n)); //mypow is my (log n) power
for(i=1 ; i<=t ; i++)
{
lastx=x;
x = x*x%n;
if(x==1 && lastx!=1 && lastx!=n1)
return false;
}
if(x!=1)
return false;
return true;
}
having 500 as output means that every odd integer in the range gets false from this function.
here is the power function also:
__int64 mypow(__int64 a , __int64 b)
{
__int64 q,r;
if(b==0) return 1;
if(b==1) return a;
q= mypow(a,b/2);
r = b%2==0 ? 1:a;
return (((q*q)%n)*r)%n;
}

 Experienced poster
 Posts: 128
 Joined: Fri Nov 15, 2002 7:45 am
 Location: Kyrgyzstan
First of all let me thank little joey for such a nice problem!
I don't remember the last time I read the problem statement with such an interest
Personally I was satisfied with Time Limit. My solution using suspect(2761,n) failed and it made me think for a while to find the right way to solve the problem with sieve.
By the way, who knows what is the upper limit for n for using suspect(2761,n) safely? And what is the optimum bases set to check for primes up to 2^64?
I don't remember the last time I read the problem statement with such an interest
Personally I was satisfied with Time Limit. My solution using suspect(2761,n) failed and it made me think for a while to find the right way to solve the problem with sieve.
By the way, who knows what is the upper limit for n for using suspect(2761,n) safely? And what is the optimum bases set to check for primes up to 2^64?
 danielrocha
 New poster
 Posts: 44
 Joined: Sun Apr 27, 2003 3:17 am
 Location: Rio Grande do Norte  Brazil
 Contact:
I agree that it was a really interesting problem (made me learn a lot of things about the MillerRabin test), but the time limit was really too tight. Anyways, thanks for the tip, i "sieved" the interval instead of testing using MillerRabin and the problem ran in half the time: 0:02.877s. We did so many bit optimizations and never occurred to us to try this...
p.s. How many bases we would have to try to make sure a number up to 2^64 is prime? Thats a really interesting question!
p.s. How many bases we would have to try to make sure a number up to 2^64 is prime? Thats a really interesting question!
Daniel
UFRN HDD1
Brasil
UFRN HDD1
Brasil
 little joey
 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Yes, it is an interesting subject. You may find more information about it by googling "strong pseudoprimes" and "primality testing". I didn't discover the triplet (2,7,61) myself, but found it in this article http://www.cryptomathic.com/company/simpledeter.html. I verified it of course before I wrote the problem. The first failure for all three bases is 4759123141 according to the article. I tried several other triplets, but none could increase this limit.
It gets increasingly time consuming to find higher limits; to do a MillerRabin test on 64 bit numbers you need to calculate with 128 bit numbers, so simple arithmetic instructions don't suffice. It is conjectured that the first failure using the first 11 primes as base is 3825 12305 65464 13051 (see http://portal.acm.org/citation.cfm?id=950446) a 19 digit number and still below 2^64.
Maybe a test using 6 or 7 numbers as base exists for 2^64, but it may take some time to find it.
It gets increasingly time consuming to find higher limits; to do a MillerRabin test on 64 bit numbers you need to calculate with 128 bit numbers, so simple arithmetic instructions don't suffice. It is conjectured that the first failure using the first 11 primes as base is 3825 12305 65464 13051 (see http://portal.acm.org/citation.cfm?id=950446) a 19 digit number and still below 2^64.
Maybe a test using 6 or 7 numbers as base exists for 2^64, but it may take some time to find it.

 Experienced poster
 Posts: 128
 Joined: Fri Nov 15, 2002 7:45 am
 Location: Kyrgyzstan

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
hmm
I made judge data for it and set time limit. Generally the twice time limit than my machine works in UVa but for this problem it became right. I actually don't set time limit running on the judge machine. So sorry! but it was an unintentional mistake.
In the end everything got tight as I found a bug in my own problem, fixed it but still there was another data type mistake. I wrote a brute force soln for "How many solutions", and tested it with smaller values so long data type in t.he judge solution did not create any problem but in actual judge data larger numbers were used so an in64 was required. So I could not find the time to write alternate for "Prime Suspect" and you know I am now not nearly as fast as many of you .
In the end everything got tight as I found a bug in my own problem, fixed it but still there was another data type mistake. I wrote a brute force soln for "How many solutions", and tested it with smaller values so long data type in t.he judge solution did not create any problem but in actual judge data larger numbers were used so an in64 was required. So I could not find the time to write alternate for "Prime Suspect" and you know I am now not nearly as fast as many of you .