bnu oj 13288 Bi-shoe and Phi-shoe

题目链接：

　　http://www.bnuoj.com/contest/problem_show.php?pid=13288

题目大意：

　　给出一个n，然后给出n个幸运数（[1,m]中不能被m整除的数的数目总和n，在[1,n]中的数称为m的幸运数），求原来的n个数的和最小是多少？

解题思路：

　　由素数的性质可以知道，素数的因子最少，所以每个幸运数的最小原数应该为素数，所以我们先把素数筛选出来，逐个比较就好啦。

代码：

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 const int N = ;

 int a[maxn], b[N];

 void isprim();

 int main ()

 {

     int t, n, m, l=;

     memset (a, , sizeof(a));

     memset (b, , sizeof(b));

     isprim();

     scanf ("%d", &t);

     while (t --)

     {

         long long sum = ;

         scanf ("%d", &n);

         while (n --)

         {

             scanf ("%d", &m);

             sum += b[a[m]];//因为在打素数表时候已经记录，所以就不用再循环寻找

         }

         printf ("Case %d: %lld Xukha\n", l++, sum);

     }

     return ;

 }

 void isprim()//筛选素数

 {

     int i, j = , k;

     for (i=; i<maxn; i++)

         if (!a[i])

         {

             b[j++] = i;//抄出素数

             for (k=i; k<maxn; k+=i)

                 a[k] = j;

         }

     j = ;

     for (i=; i<maxn; i++)

     {

         if (j < a[i])

             j = a[i];

         a[i] = j;//距离i最近的素数是第j个素数

     }

 }