质因数分解原创算法

由于这几天电脑坏掉了,这个算法是之前总结出来的,当时没来的及总结。具体就不介绍了。作用是范围内某数快速分解质因数相乘。

1
2
3
4
5
6
7
8
9
10
11
12
13
void Prime(){
memset(tag,0,sizeof(tag));
int cnt=0;
for(int i = 2; i<N; i++){
if(tag[i])
prime[cnt++]=i;
for(int j=0;j<cnt && prime[j]*i<N; j++){
tag[i*prime[j]] = i;
if(i % prime[j]==0)
break;
}
}
}

打表时表中储存为该数最小质数,这样给一个数只需除以对应表中数,直到除到最后为1为止


纸短情长啊文章结束了但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!