10956 - Prime Suspect

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10956 - Prime Suspect

Post by waelsamy » Sun Oct 30, 2005 2:55 am

could any one help me please how do i solve i recived wrong answer

User avatar
danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:

Post by danielrocha » Sun Oct 30, 2005 3:07 pm

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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Oct 30, 2005 3:14 pm

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sun Oct 30, 2005 4:43 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

Post by Bj » Sun Oct 30, 2005 11:52 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.

Renat
New poster
Posts: 10
Joined: Thu Jul 18, 2002 2:40 pm
Location: Russia
Contact:

Post by Renat » Mon Oct 31, 2005 9:37 am

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
Location: Bangladesh
Contact:

10956 sample I/O

Post by mamun » Mon Oct 31, 2005 9:47 am

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.

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

sieve

Post by taha » Mon Oct 31, 2005 10:21 am

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

Post by taha » Mon Oct 31, 2005 11:00 am

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

Post by Bj » Mon Oct 31, 2005 6:40 pm

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

Post by Andrey Mokhov » Mon Oct 31, 2005 11:01 pm

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?

User avatar
danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:

Post by danielrocha » Tue Nov 01, 2005 12:10 am

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... :oops:

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Nov 01, 2005 12:58 am

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

Post by Andrey Mokhov » Tue Nov 01, 2005 1:30 am

Thanks, I guess we can safely take first 12 primes for that :)

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » Tue Nov 01, 2005 4:39 pm

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 :).

Post Reply

Return to “Volume 109 (10900-10999)”