USER: tianbing tianbing [tbbd4261]
TASK: sprime
LANG: C++
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.011 secs, 2932 KB]
Test 2: TEST OK [0.000 secs, 2932 KB]
Test 3: TEST OK [0.000 secs, 2932 KB]
Test 4: TEST OK [0.011 secs, 2932 KB]
Test 5: TEST OK [0.011 secs, 2932 KB]
All tests OK.
Your program ('sprime') produced all correct answers! This is your
submission #7 for this problem. Congratulations!
Here are the test data inputs:
------- test 1 -------
4
------- test 2 -------
5
------- test 3 -------
6
------- test 4 -------
7
------- test 5 -------
8
Keep up the good work!
Thanks for your submission!
代码：原来写的代码在怎么优化只能过四组数据。
查了一下才知道素数有如下规律：
（来自NOCOW）
从数学的角度：
1.首位只能是质数2 3 5 7
2.其余位只能是1，3，7，9
3.若n=1，直接输出2，3，5 ，7
这样很快的就过了
/*
ID:tbbd4261
PROG:sprime
LANG:C++
*/
#include<iostream>
#include<fstream>
#include<cmath>
#include<time.h>
using namespace std;
int n;
int isprime(int n)
{ if(n<2)return 0;
if(n==2)return 1;
if(n%2==0)return 0;
for(int i=3; i<=sqrt(n); i+=2)
if(n%i==0)return 0;
return 1;
}
void dfs(int s,int k,ofstream &cout)
{
int i;
if(!isprime(s))return;
if(k==n)cout<<s<<endl;
else for(i=1; i<=9; i+=2)
dfs(s*10+i,k+1,cout);
}
int main()
{
ifstream cin("sprime.in");
ofstream cout("sprime.out");
int t1=1,t2;
cin>>n;
dfs(2,1,cout);dfs(3,1,cout);dfs(5,1,cout);dfs(7,1,cout);
//system("pause");
return 0;
}