【素数筛】分解质因数

[蓝桥杯][基础练习VIP]分解质因数

这**都是些什么奇奇怪怪的oj......

做题要用到分解质因数搜个板子做一做

大体思想：先把数据范围内的素数筛出来（get_list() ）

然后代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 const int sz = 10010;
 5 int a, b, cnt = 0;
 6 int pri[sz];
 7 bool pd[sz];
 8 void get_list() {
 9     pd[1] = pd[0] = 1;
10     for(int i = 2; i <= b; i++) {
11         if(!pd[i]) pri[++cnt] = i;
12         for(int j = 1; j <= cnt && pri[j] * i <= b; j++) {
13             pd[i * pri[j]] = 1;
14             if(i % pri[j] == 0) break;
15         }
16     }
17 }
18 void work(int x) {
19     int flag = 0, mid = x;
20     for(int i = 1; i <= cnt; i++) {
21         if(pri[i]<=mid && mid%pri[i]==0) {
22             if(!flag) {
23                 printf("%d", pri[i]);
24                 flag = 1;
25                 mid /= pri[i];    
26                 i--;//我发现我写的平方数， 如4， 9， 25此类只能输出单个质因数， 故 -- ， 再算一次是不是还能被整除
27                 if(mid == 1) break;
28             }
29             else  {
30                 printf("*%d", pri[i]);
31                 mid /= pri[i];
32                 i--;    
33                 if(mid == 1) break;
34             }
35         }
36     }
37 }
38 int main() {
39     scanf("%d%d", &a, &b);
40     get_list();
41     for(int i = a; i <= b; i++) {
42         printf("%d=", i);
43         work(i);
44         printf("
");
45     }
46     return 0;
47 }