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!
代碼：原來寫的代碼在怎么優(yōu)化只能過四組數(shù)據(jù)。
查了一下才知道素數(shù)有如下規(guī)律：
（來自NOCOW）
從數(shù)學(xué)的角度：
1.首位只能是質(zhì)數(shù)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;
}