分解质因数FZU - 1075

66 阅读 0 评论 44 点赞

我是靠谱客的博主诚心奇异果，最近开发中收集的这篇文章主要介绍分解质因数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 }