1059. Prime Factors (25)

题目:

https://www.patest.cn/contests/pat-a-practise/1059

大概描述:

给定一个数写出组成它的素数乘积

特征词:

质数  筛法

使用语言:

C++

解题思想:

素数筛法构建素数表

题目得分:

25

提交次数:

3

时间

50分钟

代码

#include<cstdio>
//假设只进行1000000以内的素数表的建立
const int MU = 500000;
const int MAXI = 500000;
bool flg[MAXI] = {0};
int p[2][MAXI];
int r = 0;
void prime_table(){
 int i = 0;
 int j = 0;
 for(i = 2;i < MU;i++){
 if(flg[i] == false){
 p[0][r++] = i;
 // printf("flg %d",i);
 for(j = i + i;j < MU;j += i){
 // printf("OOK");
 flg[j] = true;
 }
 }
 }
}
int main(){
int m = 0;
scanf("%d",&m);
prime_table();//建立了1000000以内的素数表
//printf("table is OK\n");
int i = 0;
if(m == 1){
 printf("1=1");
 return 0;
}
int k = m;
//printf("&&&&&&&&");
//printf("%d",r);
for(i = 0;i < r;i++){
 // printf("&&&&&&&&1\n");
 if(k == 1){
 // printf("&&&&&&&&2\n");
 break;
 }else{
 if(k % p[0][i] == 0){
 // printf("pp%d",p[0][i]);
 p[1][i] ++;
 k = k / p[0][i];
 i --;

 }
 }
}
int u = 0;
for(i = 0;i < r;i++){
 if(p[1][i] != 0){
 u++;
 }
}
if(k != 1){
 u++;
}
printf("%d=",m);
for(i = 0;i < r;i++){
 if(p[1][i] == 1){
 u --;
 printf("%d",p[0][i]);
 if(u != 0){
 printf("*");
 }
 }
 if(p[1][i] > 1){
 u --;
 printf("%d^%d",p[0][i],p[1][i]);
 if(u != 0){
 printf("*");
 }
 }
}
if(k != 1){
 printf("%d",k);
}
}

运行结果

25

 成长

这一题真算尽心思,其中最麻烦的部分就是在建立好素数表后,因为内存的限制所以只能建出500000以内的素数表,但是int中正数的最大值2147483647,那么对于所给的数组成它的素数一旦超出500000该怎么处理能,后来推导发现,在将给定的一个数让他输出小于500000的组成素数后,如果此时还有其他组成数,那么直接输出。例如

1000018 = 2 * 500009

那么对于在500000以内的素数因子,2会被输出而,500009则是直接被输出,为什么可以直接被输出,下面给出证明:

如果在经过500000以内因子输出后,还有其他因子a,那么这个因子a肯定是超过500000的一个数,而这个数a如果是素数那么就可以直接输出,如果这个数a并不是素数,那么组成的它的素数因子至少有两个且他们的值都大于500000,那么a的值至少为500000*500000 =250000000000 > 2147483647远远大于int 的范围因此是不可能的因此,如果存在a,那么一定是一个素数,可以直接输出。

这是我在得到了23分后想到代码可能存在的问题,思考良久,得到的可能测试点,在运行了一下后,还是23分怎么会呢,我已经想到了那么多。

突然,猛然惊悟,好像还有一个数忘了,1。

原来那个测试点并不是1000018,卧槽。

凌乱在风中…….

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注