Page **1** of **5**

### 524 - Prime Ring Problem

Posted: **Fri Oct 04, 2002 6:30 am**

by **Shahid**

hi,

i recently solved problem 524, actually i am not satisfied with my timing at all. my first timing was 3.160...not it downs to 1.360....but the still its over 1.000....so give me some suggestion..

at first i used the brute force method of finding out primes(that is diving continously till square root of the number)..and got 3.160

then i decided to generate a list of primes at the begining of the program....in generating the list at first i used sieve of iratosthinis method...and got 1.400 timing

then i used the general mehod of prime fining, the difference is i only divide the number with the primes till that number's square root

and then i got 1:360

how can i do much better?

### 524 Prime Ring Problem

Posted: **Sun Oct 20, 2002 8:26 pm**

by **rury**

In my program..

when a input number is 16, long output lines are printed.

But.. I think it is correct.

Is there any body solved this problem?

How many output lines in 16 number?

[/b][/i]

### Re: 524 Prime Ring Problem

Posted: **Mon Oct 21, 2002 4:57 pm**

by **Robbie**

rury wrote:In my program..

when a input number is 16, long output lines are printed.

But.. I think it is correct.

Is there any body solved this problem?

How many output lines in 16 number?

[/b][/i]

My program gave 81024 lines.

GGG

Posted: **Mon Oct 21, 2002 9:35 pm**

by **Shahid**

i improve my code a bit and now the time is 1.190 sec....

i improved the code of prime generation and aslo improve time by cutting down some unnecessary recursive calls.......but still weird how people solved this problem in 0.210 sec!!!!!!!!

Posted: **Tue Oct 22, 2002 3:21 pm**

by **rury**

My program gives 81024 lines in number 16, too.

But.. I got reply - "output limit exceeded".

Why?

Posted: **Tue Oct 22, 2002 6:10 pm**

by **rury**

Did you accept 524 problem?

I got a reply - output limit exceeded..

I don't know why I got it.

I'm very curious to know answer..

Help~

Posted: **Tue Oct 22, 2002 7:09 pm**

by **Robbie**

What about other inputs ?

Here is outputs from my AC program :

Code: Select all

```
2 : 1
4 : 2
6 : 2
8 : 4
10 : 96
12 : 1024
14 : 2880
16 : 81024
```

May be this will help !

Posted: **Tue Oct 22, 2002 8:49 pm**

by **Shahid**

did u think i post these messages without getting 524 accepted???

Posted: **Wed Oct 23, 2002 6:09 pm**

by **rury**

Thanks..

I got same answer for you.

I'm not wrong answer reply but.. I got output limiit exceeded.

I send you my source.

Please tell me why did I get wrong reply..

Posted: **Mon Nov 25, 2002 3:02 am**

by **jonas**

Robbie wrote:What about other inputs ?

Here is outputs from my AC program :

Code: Select all

```
2 : 1
4 : 2
6 : 2
8 : 4
10 : 96
12 : 1024
14 : 2880
16 : 81024
```

May be this will help !

I have exactly this amount of output, but I get "Wrong answer" anyway. I don't understand what's wrong.

Posted: **Mon Nov 25, 2002 2:58 pm**

by **Robbie**

May be some problems occur when you write your outputs. Please check it carefully again ....

If there exist problems, I think you should post your code here so that someone can find out your mistakes.

Posted: **Wed Dec 18, 2002 3:36 pm**

by **pc5971**

How did you solved this problem??? Did you use backtracking method? I think this method is too slow? I thought to generate the permutations of (1,2,...,n) using lexicografical order, and chek the conditions . . .

Can you give me some advice?!?

Posted: **Fri Dec 20, 2002 6:52 pm**

by **titid_gede**

i use backtracking and got AC (P.E) in 1.701 second. it'q quite fast for this case, and also by using backtracking, they automatically generate result in lexicography order.

Posted: **Mon Jan 27, 2003 12:36 pm**

by **hank**

rury wrote:My program gives 81024 lines in number 16, too.

But.. I got reply - "output limit exceeded".

Why?

I don't think there is the number "16" in the judge's test data.