蓝桥杯D1

整数因式分解的问题。了解了一下筛法计算素数的算法。之前都是直接跑的sqrt(n)...

上方的genPrime()即筛法。大致意思是开一个标识数组，通过循环，下标为合数的位置置为false。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 bool flag[10000000]; //标志一个数是否为素数
 4 int prime[100000]; //素数表,下标从0开始
 5 int size=0; //素数个数
 6 void genPrime()
 7 {
 8     int max=100000000;
 9     memset(flag, true, sizeof(flag));//首先对标签数组进行初始化，全部设为true。
10     for(int i = 2; i <= max / 2; i++)
11     {
12         if(flag[i])
13         {
14             for(int j = i << 1 ; j <= max; j += i)
15             {
16                 flag[j] = false;
17             }
18         }
19     }
20     for(int i = 2 ; i <= max; i++)
21     {
22         if(flag[i])
23         {
24             prime[size++] = i;//存储素数。将所有标志位依然为1的标志写入素数数组中去。
25         }
26     }
27 }
28 
29 int son[500];
30 int j;
31 void breakNum(int num,int arr[])
32 {
33     for(int i=0; i<sizeof(prime)/sizeof(int)&&prime[i]<=num;)
34     {
35         if(num%prime[i]==0)
36         {
37             son[j]=prime[i];
38             j++;
39             num/=prime[i];
40         }
41         else
42         {
43             i++;
44         }
45     }
46 }
47 
48 
49 int main()
50 {
51     memset(son,0,sizeof(son));
52     genPrime();
53     int num;
54     cin>>num;
55 
56     if(num==1)
57     {
58         cout<<1<<endl;
59     }
60     else
61     {
62         breakNum(num,son);
63         for(int i=0; i<j; i++)
64         {
65             if(son[i]!=0)
66             {
67                 if(i!=j-1)
68                 {
69                     cout<<son[i]<<"*";
70                 }
71                 else
72                 {
73                     cout<<son[i]<<endl;
74                 }
75             }
76         }
77     }
78     return 0;
79 }

View Code