## 10956 - Prime Suspect

Moderator: Board moderators

waelsamy
New poster
Posts: 2
Joined: Sun Oct 30, 2005 2:39 am

### 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 miller-rabin test for bases 2, 7 and 61) and are "suspect" for the given base, we add it to the failures list.
Daniel
UFRN HDD-1
Brasil

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
I agree that the time limit of 4 seconds was extreme. To get under 4 seconds, I used a prime sieve on the given interval; this runs a little bit faster than using miller rabin on all odd numbers in that interval.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Actually I didn't make the judge input (I don't know who did), I only created the problem and wrote a sample solution (which uses a sieve). I agree that the time limit looks too tight.

Bj
New poster
Posts: 24
Joined: Mon Oct 17, 2005 1:39 am
Location: Sweden
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.

Renat
New poster
Posts: 10
Joined: Thu Jul 18, 2002 2:40 pm
Location: Russia
Contact:
I used prime sieve and implemented Suspect function as it is described in problem statement. All values are stored as unsigned int (not int64). No special optimization. Time: 0:02.682.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:

### 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?

taha
New poster
Posts: 12
Joined: Mon Oct 31, 2005 10:17 am
Location: Egypt

### 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 !!!

taha
New poster
Posts: 12
Joined: Mon Oct 31, 2005 10:17 am
Location: Egypt

### 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 non-prime 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 ; (n-1)>=(((__int64)1)<<i) ; i++)
if((n-1)%(((__int64)1)<<i)==0)
t=i;

u=(n-1)/(((__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!=n-1)
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;
}

Bj
New poster
Posts: 24
Joined: Mon Oct 17, 2005 1:39 am
Location: Sweden
If you got 500 instead of 457, try to change your power mod routine to use long long internally.

Andrey Mokhov
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(2|7|61,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(2|7|61,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 Miller-Rabin test), but the time limit was really too tight. Anyways, thanks for the tip, i "sieved" the interval instead of testing using Miller-Rabin 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!
Daniel
UFRN HDD-1
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 Miller-Rabin 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.

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan
Thanks, I guess we can safely take first 12 primes for that

shahriar_manzoor