O-Reverse Prime

Can anyone tell me what am I doing wrong ? I used tutorial from TopCoder about Miller-Rabin Primality Test...

http://www.z-trening.com/submit.php?subm_stat=1&submit=7100099799

Should I try another Primality Tester or what ?

It's enough to use very simple primality, the one that check is some number divisable by prime numbers in interval [2, sqrt(number)]. You should find more efficient way to check all numbers in that interval.

how can i find reverse prime numbers other than reversing its digits and then calculating if that number is prime

Well, in this task you aren't supposed to do it faster ( I think )

The sub-problem you are supposed to do faster is to find all prime numbers in interval [A, B]...

other than checking for 2 to sqrt?

Yes...
Are you interested in solution ?

well ofc:D

I haven't done this task yet, actually I've just read it, so I'm not sure this is correct solution..

Here is my idea..

because (0 <= B - A <= 56765) it would be good if we could find all prime numbers that are >= A and <= B and for each of them look if it is reverse prime...

So if we could somehow get all prime numbers in interval [A, B] in time it would be good :)...

Number X is prime if it can't be written as multiply of two numbers greater then 1...

So, X is not prime if X = a * b for some a, b > 1
=> it is sufficient to check if X is divisible by any prime number <= sqrt( X ) and > 1..

Because X <= 1234554321 it is sufficient to check divisibility by prime numbers <= sqrt( 1234554321 ) ~ 35 000

You can find all prime numbers <= 35 000 using eratosten sieve...

For some prime number P how many numbers in interval [A, B] are divisible by him ?
It's something like ( B - A ) / P +- 1... Right ?

So, if we would for each prime number <= 35 000 check every number in interval [A, B] divisible by that prime number "not prime", every unchecked number would be prime :D

Now you have all prime numbers in interval [A, B] and for each of them look if its reverse number is also prime...

I hope I helped :D

yes ok will try it later:D

Your idea is good, you just need to do Eratosten's Sieve in interval [A, B] and then regular primality test for Reverse numbers. :)

Btw my first idea was Miller Rabin but it failed on 3 tests :/

whats that:D?

Some ultra tera giga mega super fast primality test . xDDD

http://en.wikipedia.org/wiki/Miller–Rabin_primality_test

XD will check it

I think that you have nice explanation on TopCoder and also you have the whole code in C++ ( learn it :P ) .

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=primalityTesting

going to start learning when this boring stupid school ends

@Al3kSaNdaR: Well, if you think you shouldn't go number by number from interval [A, B] and check divisibility by every prime number... Of course you shouldn't :D

You just need to check every number in interval [A, B] is it divisible by some prime number ( like I said )
And you are doing that by going only on those numbers divisible by that prime one :D