The correct answer is 55
Your versions of isCircularPrime just truncates the number ( this
is actually useful in a next problem though; )
prime_walks is a nice and efficient way to find primes ... and
not a bit n00bfriendly.
I'm not posting it anywhere, I'm just learning and having fun.
On Wednesday, 16 May 2012 at 10:38:02 UTC, Era Scarecrow wrote:
On Wednesday, 16 May 2012 at 09:46:06 UTC, Dmitry Olshansky
wrote:
On 16.05.2012 13:26, Tiberiu Gal wrote:
foreach(i; 2 .. Max) {
//writefln("is %s prime ? %s ", i, i.isPrime);
if( i.isPrime && i.isCircularPrime) {
cnt++;
Curiously i've just posted a sample (as part of another topic)
that progressively gives your larger primes. I haven't speed
tested it, but it always spits out primes.
http://forum.dlang.org/thread/jovicg$jta$1...@digitalmars.com
So your code might look like...
primes_walk pw;
pw.cap = 1_000_000;
foreach(i; pw) {
if( i.isCircularPrime) { //i is always prime
bool isCircularPrime( int n) {
auto c = to!string(n);
for(int i ; i < c.length; i++){
c = c[1 .. $] ~ c[0];
Don't ever do that. I mean allocating memory in tight cycle.
Instead use circular buffer. (just use the same array and
wrap indexes)
Hmm... I'd say this is totally written wrong... Rewriting it
to a more optimized one I got 15ms as a total running time for
1_000_000 numbers. answer I got was 3181... remember I'm not
optimizing it or anything.
If this is a gem to show the power & speed of D, by all means
use it. But I want credit for my prime_walk...
real 0m0.257s
user 0m0.015s
sys 0m0.015s
-- rewrite with prime_walk
module te35;
import std.stdio;
//prime_walk by Era Scarecrow.
//range of primes, nearly O(1) for return.
struct prime_walk {
int map[int];
int position = 2;
int cap = int.max;
int front() {
return position;
}
void popFront() {
//where the real work is done.
if ((position & 1) == 0) {
position++;
} else if (position>= cap) {
throw new Exception("Out of bounds!");
} else {
int div = position;
int p2 = position * 3;
//current spot IS a prime. So...
if (p2 < cap)
map[p2] = div;
position += 2;
//identify marked spot, if so we loop again.
while (position in map) {
div = map[position];
map.remove(position);
p2 = position;
do
p2 += div * 2;
while (p2 in map);
position += 2;
if (p2 <= cap) //skip out, no need to save larger than
needed values.
map[p2] = div;
}
}
}
bool empty() {
return position >= cap;
}
}
const Max = 1_000_000;
bool[Max] primes;
void main() {
assert(bool.init == false); //just a speedup if true.
removes 15ms
int cnt;
prime_walk pw;
pw.cap = Max; //no primes larger than 1Mil
foreach(i; pw) { //i is ALWAYS prime.
primes[i] = true; //removes need for isprime totally if we
are never going above the foreach's i
if(i.isCircularPrime) {
cnt++;
// writefln("\t\tis %s, circular prime ", i); //already
confirmed
}
}
writeln(cnt);
}
//bool isPrime(int); //removed, not needed in this case
//since it's always lower...
//removes need for string, and only uses 1 division per level
immutable int[] levels = [
//1_000_000_000, 100_000_000, 10_000_000, //completeness sake.
1_000_000, 100_000, 10_000, 1_000, 100, 10];
bool isCircularPrime(int n) {
foreach(l; levels) {
if (l > n)
continue;
if (primes[n] == false)
return false;
n %= l; //remainder of 10, sorta...
}
return true;
}
