USACO1.5Superprime Rid[附带关于素数算法时间测试]

题目描述

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

输入输出格式

输入格式：

单独的一行包含N。

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

说明

题目翻译来自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

Miller-Rabin 0.5 0.01

//
//  main.cpp
//  usaco1.5 superprime rib
//
//  Created by abc on 16/8/15.
//  Copyright © 2016年 abc. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
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<<now<<"
";
    if(now==l+1){
        for(int i=1;i<=l;i++) printf("%d",a[i]);
        printf("
");
        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;
}