hdu-2136 Largest prime factor---巧用素数筛法

时间:2022-09-08 20:49:05

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=2136

题目大意:

每个素数在素数表中都有一个序号,设1的序号为0,则2的序号为1,3的序号为2,5的序号为3,以此类推。现在要求输出所给定的数n的最大质因子的序号,0<n<1000000。

解题思路:

一开始用暴力超时,想到利用素数筛法,在筛素数的同时,每筛出一个素数就对之后的位置进行染色,比如2就对2的所有倍数染色,染成2的序号,3也是这样,而且会覆盖之前一部分2所染的地方,这样正好符合题意,求的是最大的素因子的位置序号。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<queue>
 7 #include<stack>
 8 #include<map>
 9 #include<sstream>
10 #define Mem(a, b) memset(a, b, sizeof(a))
11 using namespace std;
12 typedef long long ll;
13 const int INF = 1e9 + 7;
14 const int maxn = 1000000+10;
15 int ans[maxn];
16 bool is_prime[maxn];
17 int sieve(int n)//返回n以内素数的个数
18 {
19     int p = 0;
20     for(int i = 0; i <= n; i++)is_prime[i] = 1;
21     is_prime[0] = is_prime[1] = 0;
22     for(ll i = 2; i <= n; i++)
23     {
24         if(is_prime[i])
25         {
26             p++;
27             ans[i] = p;
28             for(ll j = 2 * i; j <= n; j += i)is_prime[j] = 0, ans[j] = p;
29         }
30     }
31     return p;
32 }
33 int main()
34 {
35     int tot = sieve(1000000);
36     int n;
37     while(scanf("%d", &n) != EOF)
38     {
39         if(n == 1)
40         {
41             printf("0\n");
42             continue;
43         }
44         printf("%d\n", ans[n]);
45     }
46     return 0;
47 }