题目描述

农民约翰的母牛总是产生最好的肋骨。你能通过农民约翰和美国农业部标记在每根肋骨上的数字认出它们。农民约翰确定他卖给买方的是真正的质数肋骨,是因为从右边开始切下肋骨,每次还剩下的肋骨上的数字都组成一个质数,举例来说: 7 3 3 1 全部肋骨上的数字 7331是质数;三根肋骨 733是质数;二根肋骨 73 是质数;当然,最后一根肋骨 7 也是质数。 7331 被叫做长度 4 的特殊质数。写一个程序对给定的肋骨的数目 N (1<=N<=8),求出所有的特殊质数。数字1不被看作一个质数。

输入输出格式

输入格式：

单独的一行包含N。

输出格式：

按顺序输出长度为 N 的特殊质数,每行一个。

输入输出样例

输入样例#1：

4

输出样例#1：

2333233923932399293931193137373337393793379759397193733173337393

说明

题目翻译来自NOCOW。

USACO Training Section 1.5

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

第一位一定是2,3,5,7 ，以后各位只能是单数，并且不能是5，直接dfs每一位，只要不是prime就退出

用哪个方法判素数呢？

一开始随手打了欧拉筛法，结果MLE＋TLE，又改了个朴素算法，结果AC了....

对于n等于8，其实只有4^8=65536次检测，太少了，即使根号n的复杂度，合起来是16777216，欧拉筛法却要10^8

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

于是我开始测速玩，测试环境MacBook Air13

n=1e8，我实现的Euler筛法要跑1.3s左右，Eratosthenes筛法要近3s......然而，朴素竟是1.1s，Miller-Rabin只要0.5s；

Miller-Rabin完虐Euler筛法暂且不说，为什么朴素方法也比Euler筛法快，O(n根号n)与O(n)没法比吧..........这是玄学

n=1e6，Eratosthenes筛法0.5s，Euler筛法0.016s，朴素也在0.016s左右，Miller-Rabin只要0.01s

这是要Eratosthenes筛法情何以堪

------------------------------------------------------------------------------------------------------------------------------------------------------------

［2016-08-19更新］：

都是memset惹的祸,去掉后Eratosthenes n=1e8是2.26s，n=1e6可以0.021s，朴素也是0.021，然而Euler筛法却0.026s还是玄学

 

------------------------------------------------------------------------------------------------------------------------------------------------------------

 

 上面说的太乱了，总结一下：

分别是n=1e8 n=1e6

朴素 1.2s 0.03s

Eratosthenes筛法 2.26s 0.021s

Euler筛法 1.4s 0.016s

0.5 0.01

 

 

////  main.cpp//  usaco1.5 superprime rib////  Created by abc on 16/8/15.//  Copyright © 2016年 abc. All rights reserved.//#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int N=1e8+5,L=10;int n=1,l;//bool flag[N];int prime[N];int st[4]={
    2,3,5,7},odd[4]={
    1,3,7,9},a[L];//int es(int n){//    int cp=0;//    for(int i=2;i<=n;i++){//        if(!flag[i]) prime[++cp]=i;//        for(int j=1;j<=cp&&prime[j]*i<=n;j++){//            flag[i*prime[j]]=1;//            if(i%prime[j]==0) break;//        }//    }//    return cp;//}inline int flag(int n){    int m=sqrt(n)+1;    for(int i=2;i<=m;i++) if(n%i==0) return 1;    return 0;}void dfs(int now,int v){
    //cout<
          
           <<"\n"; if(now==l+1){ for(int i=1;i<=l;i++) printf("%d",a[i]); printf("\n"); return; } for(int i=0;i<4;i++){ a[now]=odd[i]; if(flag(v*10+a[now])==0) dfs(now+1,v*10+a[now]); }}int main(int argc, const char * argv[]) { cin>>l; for(int i=1;i<=l;i++) n=10*n; //es(n); for(int i=0;i<4;i++){ memset(a,0,sizeof(a)); a[1]=st[i]; dfs(2,st[i]); } return 0;}