HDU 1216 Assistance Required 埃拉托色尼色筛法

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1216

思路：色筛法

代码（1）：

 1 #include<iostream>//--------1216 HDU   埃拉托色尼筛选法
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 #include<algorithm>
 5 #include<math.h>
 6 #include<string.h>
 7 #include<vector>
 8 using namespace std;
 9 #define Max 40000
10 bool b[Max];
11 __int64 a[Max], c;
12 void fun()
13 {
14     __int64 i, j, count;
15     c = 0;
16     memset(b, true, sizeof(b));
17     b[1] = 0;
18     for (i = 2; i < Max; ++i)
19     {
20         if (b[i])
21         {
22             a[++c] = i;
23             count = i;
24             for (j = i+1; j < Max; ++j)
25             {
26                 if (b[j] == true)
27                     count--;
28                 if (count == 0)
29                 {
30                     b[j] = false;
31                     count = i;
32                 }
33             }
34         }
35     }
36 }
37 int main()
38 {
39     fun();
40     int n;
41     while (scanf("%d", &n) != EOF)
42     {
43         if (n == 0)
44             break;
45         else
46             printf("%d
", a[n]);
47     }
48     return 0;
49 }

View Code

基本类似的另外一种：

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstdlib>
 4 #include<string.h>
 5 #include<algorithm>
 6 #include<math.h>
 7 using namespace std;
 8 #define Max 40000
 9 __int64 ans[Max];
10 __int64 pop[3001];
11 void dfs()
12 {
13     __int64 i, j, count;
14     for (i = 2; i < Max; i++)
15     {
16         ans[i] = i;
17     }
18     for (i = 2; i < Max; i++)
19     {
20         if (ans[i] != 0)
21         {
22             count = i;
23             for (j = i + 1; j < Max; j++)
24             {
25                 if (ans[j] != 0)
26                     count--;
27                 if (count == 0)
28                 {
29                     ans[j] = 0;
30                     count = i;
31                 }
32             }
33         }
34         
35     }
36     j = 2;
37     for (i = 1; i <= 3000; i++)
38     {
39         while (ans[j] == 0)
40         {
41             j += 1;
42         }
43         if (ans[j] != 0)
44         {
45             pop[i] = ans[j];
46             j += 1;
47         }
48     }
49 }
50 int main()
51 {
52     dfs();
53     int n;
54     while (scanf("%d", &n)&&n)
55     {
56             printf("%d
", pop[n]);
57     }
58     return 0;
59 }

View Code