UVA 1434 - YAPTCHA

题目链接

题意：求出题目中那个公式的答案

思路：
当3?k+7非素数的时候，那么(3?k+6)!(因为必然能找到两个因子相乘)
所以原式为0

当3?k+7为素数的时候，根据威尔逊定理，((3?k+6)!+1)%(3?k+7)==0，因此原式可以转化为[x - (x - 1)] = 1

因此问题转化为只要判断3 * k + 7是不是素数，那么就很好办了，预处理出素数表，再预处理出答案即可

代码：

#include 
  
   
#include 
   
     const long long N = 1000005; bool ispri[N * 3]; int ans[N], t, n; int main() { for (long long i = 2; i < N * 3; i++) { if (ispri[i]) continue; for (long long j = i * i; j < N * 3; j += i) ispri[j] = true; } for (int i = 2; i < N; i++) ans[i] = ans[i - 1] + (!ispri[3 * i + 7]); scanf("%d", &t); while (t--) { scanf("%d", &n); printf("%d\n", ans[n]); } return 0; }