C语言经典算法：如何较快的分解质因数

Python017

C语言经典算法：如何较快的分解质因数,第1张

将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。初级算法：#include

#include

#include

int

main()

{

int

n,i

scanf("%d",&n)

printf("%d=",n)

for(i=2i<=sqrt(n)i++)

{

if(n%i==0)

{

n/=i

printf("%d*",i--)

}

}

printf("%d\n",n)

system("pause")

return

0

}

改进版：#include

#include

#include

int

main()

{

int

n,i

scanf("%d",&n)

printf("%d=",n)

while(n%2==0){

printf("%d*",2)

n/=2

}

for(i=3i<=sqrt(n)i+=2)

{

if(n%i==0)

{

n/=i

printf("%d*",i)

i-=2

}

}

printf("%d\n",n)

system("pause")

return

0

}

因为在所以的质数中只有2是偶数外，其他的质数都是奇数。所以i可以一次+2跳过所有的偶数。不过2要特别处理。待续未完。相信还有更好的算法。

#include <stdio.h>

void main(){

int i,j,k,m,n

scanf("[%d,%d]",&m,&n)

for(i=mi<=ni++)

{

k=i

printf("%d=",k)

for(j=2j<=kj++)

while(k!=j)

{

if(k%j==0)

{

printf("%d*",j)

k/=j

}

else break

}

printf("%d\n",j-1)

}

}