967 - Circular

sohel · Post by **sohel** » Fri Nov 03, 2006 10:20 am

Seems it is the first post of this problem. Circular

Isn't it true that all the valid numbers consist only the digits {1, 3, 5, 7}.

I basically generated all the numbers in the range [100, 1000000) using recursion and checked the validity. But I am getting WA.

Input: 100 999999
Output: 42 Circular Primes.

Is it correct?

stubbscroll · Post by **stubbscroll** » Fri Nov 03, 2006 10:30 am

Your answer is correct, but there are many valid numbers containing 9 (and none containing 5).

Did you remember to output Prime without an ending s when the answer is one? It's the only trap I can think of.

sohel · Post by **sohel** » Fri Nov 03, 2006 10:34 am

ooopss..

I meant to write { 1, 3, 7, 9}.. and not {1, 3, 5, 7}
any other ideas?

[Edit]: got accepted.... made a stupid/silly mistake in printing.

mpi · Post by **mpi** » Fri Nov 03, 2006 11:51 pm

i'm following the same approach than you and i always get TLE. After generating all circular primes between 100..1000000, i only have to do a simple iteration through my array and count the 1's. It's simple, but however i get TLE.

rio · Post by **rio** » Sat Nov 04, 2006 12:14 am

mpi wrote:i only have to do a simple iteration through my array and count the 1's.

This approach is too slow. Think about it. (there are just fourty few cir-primes)

mpi · Post by **mpi** » Sat Nov 04, 2006 12:53 am

You are right. There are only 42 numbers. What i was thinking about?

Now i get AC in 0.674s.

Thanks

farzane · Post by **farzane** » Thu Nov 09, 2006 10:59 pm

could someone please help me and tell me what's wrong with this code?
I'm getting WA.It is an easy problem I think so.

Code: Select all

removed

rio · Post by **rio** » Fri Nov 10, 2006 6:22 am

cir[9] = 917, but its not a prime.So check why this number pass your Circular prime test.

farzane · Post by **farzane** » Fri Nov 10, 2006 1:13 pm

Thank you very much rio.I found my mistake ang got AC.

Rupak · Post by **Rupak** » Wed Mar 07, 2007 10:20 am

I think i can't understand the problem statements .

For 917 we should check the numbers 917, 179 and 791 .
Here 917 isn't prime, 179 is prime and also 791 isn't prime .
So can we call the number 917 be a circular prime ?

helloneo · Post by **helloneo** » Wed Mar 07, 2007 10:30 am

No, 917 is not a circular prime.. because 917 and 791 is not a prime as you said..

sumantbhardvaj · Post by **sumantbhardvaj** » Fri Jun 01, 2007 6:06 pm

Somebody plz provide me some test case.. I m constantly getting wrong answer for this problem..thanx in advance

little joey · Post by **little joey** » Fri Jun 01, 2007 6:39 pm

I don't think there are any special cases. If you find 42 circular primes between 100 and 1000000, as mentioned above, you have a very good chance that your program is right. Your only worry then is to get the output format right. Have you carefully checked your output for the sample input?

sumantbhardvaj · Post by **sumantbhardvaj** » Fri Jun 01, 2007 6:43 pm

yeah ! you are absolutely right. I was not printing correctly when we have output 1. later on i found the mistake and got AC

.why do acm problems have such irrelevant output formats.. i nearly wasted 1 hr for that.

hamedv · Post by **hamedv** » Sat Jul 28, 2007 5:12 pm

i got wa.
what's wrong with my code???

Code: Select all

ACed

OJ Board

967 - Circular

967 - Circular

oooppsss