GitBook

这里写图片描述 这里写图片描述

似乎是第一次用到了素数打表法 掌握了还是挺简单的

#include<stdio.h>
int sum(int m) {
	int sum=0;
	while(m!=0) {
		sum+=m%10;
		m=m/10;
	}
	return sum;
}
int a[1000010]= {0};
int b[1000010]= {0};
int main() {
	int m,k;
	for(m=2; m<=1000000; m++) {
		if(!a[m]) {
			for(k=m+m; k<=1000000; k+=m) {
				a[k]=1;
			}
		}
	}
	for(k=2; k<=1000000; k++) {
		b[k]=b[k-1];
		if(!a[k]) {
			if(!a[sum(k)]) {
				b[k]++;
			}
		}
	}
	int i,T,L,R;
	scanf("%d",&T);
	for(i=1; i<=T; i++) {
		scanf("%d %d",&L,&R);
		printf("Case #%d: %d\n",i,b[R]-b[L-1]);
	}
	return 0;
}

题目地址:【杭电】[4548]美素数