记录编号	197643	评测结果	AAAAAAAAAAA
题目名称	[USACO Jan07] 有限制的素数	最终得分	100
用户昵称	zjh001	是否通过	通过
代码语言	C	运行时间	0.192 s
提交时间	2015-10-24 10:25:55	内存使用	23.18 MiB

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

int p[2000010];
int tag[4000010];
int n,m,d,sum,cnt = 0;

void get_prime()
{
    int i,j;
    for (i = 2; i <= m; i++)
    {
        if (!tag[i])    p[cnt++] = i;
        for (j = 0; j < cnt && p[j] * i <= m; j++)
        {
            tag[i*p[j]] = 1;
            if (i % p[j] == 0)
                break;
        }
    }
}

int ok(int k)
{
    while (k>0)
    {
          if (k%10==d) return 1;
          k/=10;
    }
    return 0;
}

int main()
{
    int i,j;
    
    freopen("qprime.in","r",stdin);
    freopen("qprime.out","w",stdout);
    
    scanf ("%d%d%d",&n,&m,&d);
    
    get_prime();
    
    for (i=0;i<cnt;i++)
        if (p[i]>=n) break;

    for (i;p[i]<=m && i<cnt;i++)
    {
        if (ok(p[i])==1)
           sum++;
    }
    
    printf ("%d\n",sum);
    
    return 0;
}