不判断素数快了300多毫秒
by wangsijie @ 2021-02-13 19:27:55
@[NSObject](/user/357545) 分解质因数真的不用判断素数啊
by Mobius127 @ 2021-02-13 19:28:52
帮你贴个代码
```cpp
#include<bits/stdc++.h>
using namespace std;
//Fibonacci 斐波那契
int n;
int Fibonacci[64];
bool flag=false;
/*int tmp;
int ss(int n)
{
int i;
for(i=3;(i*i)<=n;i+=2) if((n%i)==0) break;
if((i*i)<=n) return 0;
else return 1;
}突然赶脚用不着*/
int main()
{
//freopen("0.in","r",stdin);
//freopen("0.out","w",stdout);
int i;
scanf("%d",&n);
Fibonacci[1]=1;
Fibonacci[2]=1;
for(i=3;i<64;i++) Fibonacci[i]=(Fibonacci[i-1]+Fibonacci[i-2])%(1<<31);
printf("%d=",Fibonacci[n]);
while((Fibonacci[n]%2)==0)
{
if(flag==true) printf("*");
printf("2");
Fibonacci[n]/=2;
flag=true;
}
for(i=3;i<=Fibonacci[n];i+=2)
{
if(Fibonacci[n]==1) break;
while((Fibonacci[n]%i)==0)
{
//tmp=ss[i];
if(flag==true) printf("*");
printf("%d",i);
Fibonacci[n]/=i;
flag=true;
}
}
//fclose(stdin);
//fclose(stdout);
return 0;
}
```
by 小小小朋友 @ 2021-02-13 19:29:04
@[wangsijie](/user/307586) 建议重学分解质因数
by Mobius127 @ 2021-02-13 19:29:16
分解质因数为什么要判素数啊
by Mine_King @ 2021-02-13 20:03:02
不用判断素数
每次都把能第一个整除n的数全除掉了
那显然再出现的能第一个整除之前的那个数的一定是素数
by hyf9134 @ 2022-05-05 20:29:30