分解质因数FZU - 1075
题目简述：就是给一个数，把他拆分成多个素数的乘积，这正好是算术基本定理。本题我的解决方法是埃氏素数筛+质因数保存。。。开始T掉了，是因为我在最后枚举了素数，保存他们的次数，然后两次for去查询他们的次数这样需要遍历前面所有素数。显的十分浪费时间，因为如果给的数非常大，并且次数小的次数很多那么我们外面的第一层FOR就是N第二层是一个遍历内部次数输出也达到挺大程度（素数小的并且多的化N*M会很大）加上T的话很可能会超时，其实直接保存质因数在另一个素数就可以了，然后遍历输出即可(在此警醒自己，做题不要拿着题目就开做直接暴力，要精简算法的复杂程度，理清思路，这样避免后面来改动)
算术基本定理可表述为：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积
最后上代码
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 using namespace std; 5 const int MAXN=65536; 6 bool isPrim[MAXN]; 7 int prime[MAXN]; 8 int cnt[MAXN]; 9 int sum,cnt1; 10 void initPrime() 11 { 12 int i; 13 memset(isPrim,0,sizeof(0)); 14 isPrim[0]=0; 15 isPrim[1]=0; 16 int k=0; 17 for (i=2; i<MAXN; i++) 18 { 19 if (!isPrim[i]) 20 { 21 prime[k++]=i; 22 int j=2; 23 while (i*j<MAXN) 24 { 25 isPrim[i*j]=1; 26 j++; 27 } 28 } 29 } 30 sum=k; 31 return; 32 } 33 void sovl(int x) 34 { 35 for (int i=0; ; i++) 36 { 37 if (prime[i]>x)break; 38 while (x % prime[i]==0) 39 { 40 cnt1++; 41 cnt[cnt1]=prime[i]; 42 x=x/prime[i]; 43 } 44 } 45 return; 46 } 47 int main() 48 { 49 initPrime(); 50 int t,num,time; 51 scanf("%d",&t); 52 while (t--) 53 { 54 memset(cnt,0,sizeof(cnt)); 55 scanf("%d",&num); 56 time=0; 57 cnt1=0; 58 sovl(num); 59 for (int i=1; i<=cnt1; i++) 60 { 61 time++; 62 if (time==1) 63 { 64 printf("%d",cnt[i]); 65 } 66 else 67 printf("*%d",cnt[i]); 68 } 69 printf("\n"); 70 } 71 return 0; 72 }
Momenta公司福利 296人发布
