C++循环素数问题求优化
本帖最后由 ontseason 于 2013-10-16 11:20:56 编辑

/*
数字197可以被称为循环素数，因为197的三个数位循环移位后的数字：
197,971,719均为素数。100以内这样的数字包括13个，2,3,5,7,11,13,
17,31,37,71,73,79,97。要求大家算出1000000以内一共有多少个这样的
循环素数。 CPU用时限制: 10s
*/
#include <iostream>
#include <ctime>
const int MAX = 1000000;
const int mLen = 7;
int digits[mLen*2]; 
using namespace std;

int IsPrime(int n)
{
int i = 2;
for (int i = 2; i < n; i++)
if (n % i == 0)
return 0;
return 1;
}

int IsOk(int n)
{
int i = 0;
while (0 != n)
{
digits[mLen - ++i] = n%10;
n /= 10; 
}
int j = 0;
while (0 != --i)
{
digits[mLen + j++] = digits[mLen - 1-i];

for (int t = mLen - i; t < mLen + j; t++)
 n = n*10 + digits[t];
if (!IsPrime(n))
return 0;
n = 0;
}
return 1;
}
int main ()
{
clock_t start, end;
start = clock();
int cnt = 0;
for (int i = 2; i < MAX; i++)
if (IsPrime(i) && IsOk(i))
{
cout << i << endl; 
cnt++;
}
cout << cnt << endl;
end = clock();
cout << "耗时：" << (end - start) / CLOCKS_PER_SEC << endl; 
return 0;
}
//耗时200s... 求优化方法啊

[解决办法]
参考http://blog.csdn.net/turingo/article/details/8161061

引用:

/*
数字197可以被称为循环素数，因为197的三个数位循环移位后的数字：
197,971,719均为素数。100以内这样的数字包括13个，2,3,5,7,11,13,
17,31,37,71,73,79,97。要求大家算出1000000以内一共有多少个这样的
循环素数。 CPU用时限制: 10s
*/
#include <iostream>
#include <ctime>
const int MAX = 1000000;
const int mLen = 7;
int digits[mLen*2]; 
using namespace std;

int IsPrime(int n)
{
int i = 2;
for (int i = 2; i < n; i++)
if (n % i == 0)
return 0;
return 1;
}

int IsOk(int n)
{
int i = 0;
while (0 != n)
{
digits[mLen - ++i] = n%10;
n /= 10; 
}
int j = 0;
while (0 != --i)
{
digits[mLen + j++] = digits[mLen - 1-i];

for (int t = mLen - i; t < mLen + j; t++)
 n = n*10 + digits[t];
if (!IsPrime(n))
return 0;
n = 0;
}
return 1;
}
int main ()
{
clock_t start, end;
start = clock();
int cnt = 0;
for (int i = 2; i < MAX; i++)
if (IsPrime(i) && IsOk(i))
{
cout << i << endl; 
cnt++;
}
cout << cnt << endl;
end = clock();
cout << "耗时：" << (end - start) / CLOCKS_PER_SEC << endl; 
return 0;
}
//耗时200s... 求优化方法啊

[解决办法]
for (int i = 2; i < n; i++)
修改为 for (int i = 2; i*i <= n; i++)
其他小优化应该有很多，不过这里大概是能省很多的