ITSA7

#include<stdio.h>
#include<stdlib.h>

int mark[50000], prime[50000], Pt = 0;

void sieve (){
 int i, j;
 for(i = 2; i <50000; i++) {
  if(mark[i] == 0) {
   prime[Pt++] = i;
   for(j = 2; j*i<50000; j++)
    mark[j*i] = 1;
  }
 }
}



int main(){
sieve();
int n,i;
scanf("%d",&n);
printf("%d=",n);
int tmp=n;
int p[200],pow[200],top=0;

for(i=0;prime[i]*prime[i]<tmp&&n;i++){
    if(n%prime[i]==0){
        p[top]=prime[i],pow[top]=0;
        while(n%prime[i]==0){
            n=n/prime[i];
            pow[top]++;
        }
        top++;
    }
}
if(top==0)
    printf("%d^1",n);
else{
    printf("%d^%d",p[0],pow[0]);
    for(i=1;i<top;i++)
        printf("*%d^%d",p[i],pow[i]);
}
puts("");
return 0;
}

這是許沁憲簡化版本的質因數分解

#include<stdio.h>
#include<stdlib.h>
int main()
{

int flag;
int g,num,i,n,x;
int p[100],pow[100],nc=0;

scanf("%d",&num);
printf("%d=",num);
n=num;
for(i=0;num%2==0;num=num/2,i++);
if(i>0)
p[nc]=2,pow[nc]=i,nc++;

for(g=3;g*g<=n && g<=num;g=g+2){
for(i=0;num%g==0;i++,num=num/g);
if(i>0)
p[nc]=g,pow[nc]=i,nc++;
}

if(num!=1) 
p[nc]=num,pow[nc]=1,nc++;


for(i=0;i<nc;i++){
if(i!=0)
printf("*");
printf("%d^%d",p[i],pow[i]);
}
printf("\n");
system("pause");
}