2728 - 一个可怕的问题
为了鼓励小明学习数学，他的妈妈给他一个月的某一个天是质数的甜蜜糖果。 小明是高兴。但几天后，他的母亲修改了规则，只有当该月的天是一个素数和月份也是一个素数，才能拿到一个糖果。他觉得有点不高兴，因为他能得到很少的糖果。更糟的是，他的母亲又改变了规则，他不得不回答一个问题：他可以得到一个糖果在那些日子里。现在的问题是，有多少糖果，他可以得到在给定的时间间隔。 小明想哭，问你的帮助。他答应给你一半的糖果，如果你能帮助他解决这个问题。
Input
有多个测试用例。输入的第一行是一个整数T（0 <T < = 50 ），表示测试用例的数目。接下来每一行包含两个日期，问题的间隔天数。日期的格式为“ YYYY MM DD ” 。你可以假设这两个日期是有效的。 小明出生于1000年1月1日及2999年12月31日之后就不会死，所以查询都在这个区间。
小明似乎看起来不像一个地球人，但是日历跟我们平时使用的是一样的。也就是说，你需要确定闰年，其中二月份有29天。闰年可以被4整除不能被100整除，或者被400整除。
Output
输出在这个时间间隔内小明能得到的糖果数量，该区间的2边都包含在内。
Examples
Input
2 1000 01 01 1000 01 31 2000 02 01 2000 03 01
Output
0 10
Solution C++
#include <stdio.h> int prime(int n) { if(n == 2) return 1; else if(n < 2) return 0; for(int i = 2 ; i * i <= n ; i ++) if(n % i == 0) return 0; return 1; } int Leap(int n) { if((n % 4 == 0 && n % 100 != 0) || n % 400 == 0) return 1; return 0; } int monthday(int n,int m) { if(n == 2) { if(Leap(m)) return 29; else return 28; } if(n <= 7) { if(n % 2 == 1) return 31; else return 30; } else { if(n % 2 == 0) return 31; else return 30; } } int yearday(int n) { int num = 0; for(int i = 1 ; i <= 12; i ++) { if(prime(i)) { for(int j = 1 ; j <= monthday(i,n) ; j ++) if(prime(j)) num++; } } return num; } int count(int year, int m1, int m2, int n1, int n2) { int i, j, num = 0, s, e; for(i = m1 ; i <= m2; i ++) { if(prime(i)) { if(i == m1) s = n1; else s = 1; if(i == m2) e = n2; else e = monthday(i,year); for(j = s ; j <= e ; j ++) if(prime(j)) num++; } } return num; } int main () { //freopen("A.in", "r", stdin); //freopen("A.out", "w", stdout); int re, y1, y2, m1, m2, n1, n2, i, j; scanf("%d",&re); while(re--) { int num = 0; scanf("%d%d%d%d%d%d",&y1,&m1,&n1,&y2,&m2,&n2); if(y1 == y2) { if(m1 == m2) { if(prime(m1)) { for(i = n1 ; i <= n2 ; i ++) { if(prime(i)) num++; } } } else { num+= count(y1,m1,m2,n1,n2); } } else { for(i = y1 ; i <= y2 ; i ++) { if(i == y1) { num += count(i,m1,12,n1,31); } else if (i == y2) { num += count(i,1,m2,1,n2); } else { num += yearday(i); } } } printf("%d\n",num); } return 0; }