Project Euler 35

Mathematica C/C++ 
197は巡回素数と呼ばれる. 桁を回転させたときに得られる数 197, 971, 719 が全て素数だからである.

100未満には巡回素数が13個ある: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, および97である. 100万未満の巡回素数は何個か?

Mathematica

A = {};

For[i = 2, i < 1000000, i++,
  
  tmp = Table[
    FromDigits[RotateLeft[IntegerDigits[i], j]], {j, 0, 
     Length[IntegerDigits[i]]}
    ];
  
  If[MemberQ[PrimeQ[tmp], False],
   {},
   A = Append[A, i]]
]

Length[A]

さて、これで答えは出せます。
IntegerDigitsで各桁をリストに分解、tmpには桁を回転させた数全てが入ります。
下のIf文で素数かどうかを判定します。が、これではさすがに遅すぎます。
For文をTiming関数で測ったところ、42.3秒。もうちょっと早くするように考えてみました。

A = {2};

For[i = 3, i < 1000000, i += 2,
  
  tmp = Table[
    FromDigits[RotateLeft[IntegerDigits[i], j]], {j, 0, 
     Length[IntegerDigits[i]]}
    ];
  
  If[MemberQ[PrimeQ[tmp], False],
   {},
   A = Append[A, i]]
]
 
Length[A]

第2案。2以外は偶数の素数はないんだから、2は最初から除外して、 i+=2 にしてしまえ！というのがこれ。
当然ながら単純に半分、21.7秒になりました。

A = {2};

For[i = 3, i < 1000000, i += 2,
  
  If[MemberQ[OddQ[IntegerDigits[i]], False], Continue[]];
  
  tmp = Table[
    FromDigits[RotateLeft[IntegerDigits[i], j]], {j, 0, 
     Length[IntegerDigits[i]]}
    ];
  
  If[MemberQ[PrimeQ[tmp], False],
   {},
   A = Append[A, i]]
]

Length[A]

第3案。桁を回転したもの全てが素数でなければいけないということは、各桁に1つでも偶数が入っていればその数は巡回素数ではない、ということですから、
まずは各桁が全て奇数かどうかを判定してみました。
計算時間は5.2秒。最初よりはだいぶよくなりました。


しかし、随分とIf文がまだ多すぎて重い気がしますし、そもそもMathematicaで手続き的に書くと圧倒的に速度が遅くなってしまうので、なにかもっと良い方法があるはずです、それこそ0.1秒クラスで終わるような方法が。


C/C++

#include <iostream>
#include <mpir.h>
#include <deque>
#include <cmath>
using namespace std;

deque<bool> p;

/*
maxまでの素数を計算する。
あらかじめ 
deque<bool> p; 
をグローバルで宣言しておいてね
*/
void calc_prime(const int max){
	for(int i=0 ; i<max+1 ; i++){
		p.push_back(true);
	}
	p[0] = false;
	p[1] = false;

	double myEnd = sqrt(double(max));
	for(int i=2 ; i < myEnd ; i++){
		for(int j=2 ; i*j<=max ; j++){
			p[i*j] = false;
		}
	}
}

// nが素数かどうか
bool is_prime(int n){
	return p[n];
}

// nの桁数を返す。
int int_digits(int n){
	int count = 0;
	while(n!=0){
		n /= 10;
		count++;
	}
	return count;
}

// nが巡回素数かどうか
bool is_circular(int n){
	int k = n, tmp;
	int dig = int_digits(n);

	for(int i=0 ; i<dig ; i++){
		tmp = k%10;
		k /= 10;
		k += tmp * (int)powl(10,dig-1);

		if(!is_prime(k)) return false;
	}
	return true;
}

int main(){
	calc_prime(1000000);

	int count = 0;
	for(int i=1 ; i<1000000 ; i++){
		if(is_circular(i)){
			cout << i << endl;
			count++;
		}
	}

	cout << endl << count << endl;

	int end;
	cin >> end;
	return 0;
}

関数がいろいろ増えちゃった。is_circularと素数計算を組み合わせたら絶対もっと早くなるよなぁ・・・どこかの桁に偶数があったらその時点で巡回素数ではないので。