一个十进制数, 如果是素数, 而且它的各位数字和也是素数, 则称之为 "美素数", 如 29, 本身是素数, 而且 2+9 = 11 也是素数, 所以它是美素数.
给定一个区间, 你能计算出这个区间内有多少个美素数吗?
每行输入两个整数 L,R(1<= L <= R <= 1000000), 表示区间的左值和右值.
- #define maxn 1000000+1
- int num[maxn];
- bool prime[maxn];
- void getprime()
- {
- memset(prime,true,sizeof(prime));// 一开始假定所有数都是素数
- prime[1]=false;//1 肯定不是素数
- int m=sqrt(maxn);
- for(int i=2;i<=m;i++){
- if(prime(i)){
- for(int j=i+i;j<maxn;j=j+i)
- { prime[j]=false;}
- }
- }
- }
- int getsum(int n)
- {
- int sum=0;
- while(n>0){
- sum+=n%10;
- n/=10;
- }
- return sum;
- }
- int main()
- {
- int cnt=0;
- memset(num,0,sizeof(num));
- for(int i=1;i<maxn;i++){
- if(prime[i]&&prime[getsum(i)]){
- cnt++;
- }
- num[i]=cnt;
- }
- cout<<a[r]-a[l-1]<<endl;
- }
来源: http://www.jianshu.com/p/cbb0024d387b