最小公倍數 [輸出可大數]
輸入的數不可超過int 但是答案可以超過int
最多只能輸入2147483647這種數字做最小公倍數的運算
範例輸入:
1 2 3 5 6 7 8 0
範例輸出 :
6 840
/*************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
char x[10000000];
main()
{
int a,b,c,d;
long long int math[5200]={0};
int m=1;
math[0]=2;
for(a=3;a<50000;a=a+2)/*5W*5W已經2.5E 無須建更大*/
{
int flag=0;
for(b=0;math[b]<=sqrt(a);b++)
{
if(a%math[b]==0)
{
flag=1;
break;
}
}
if(flag==0)
{
math[m]=a;
m++;
}
}
while(gets(x)!=0)
{
a=strlen(x);
if(x[0]=='0'&&strlen(x)==1) break;
if(strlen(x)==0) continue;
long long int temp1=0,max=0;
long long int ans[1001]={0},top=0;
long long int ans2[101]={0}; ans2[0]=1;
/*我不會內建的參數判斷 所以我用分析的*/
for(c=0;c<a;c++)
{
if(x[c]<=57&&x[c]>=48)
temp1=temp1*10+x[c]-48;
else
{
ans[top]=temp1;
top++;
if(temp1>=max)
max=temp1;
temp1=0;
}
}
ans[top]=temp1;
top++;
if(temp1>=max)
max=temp1;
/*國中交的除法 找一個數去做除 全部都除一次 但是4的話 可能/2 剩2 那麼會跑到3 所以要重跑一次*/
for(a=0;a<m&&math[a]<max;a++)
{
int flag=0;
for(b=0;b<top;b++)
{
if(ans[b]%math[a]==0)
{
ans[b]/=math[a];
flag=1;
}
}
if(flag==1)
{
for(c=0;c<100;c++)
ans2[c]*=math[a];
for(c=0;c<100;c++)
if(ans2[c]>=10)
{
ans2[c+1]=ans2[c+1]+ans2[c]/10;
ans2[c]%=10;
}
a--;
}
}
/*將同樣大的質數消掉*/
for(a=0;a<top;a++)
for(b=a+1;b<top;b++)
if(ans[a]==ans[b])
ans[b]=1;
/*大數乘法 原因 9 * 2147483647 用unsigned long long 也會暴 把剩下的大於5萬的質數 相乘起來*/
for(a=0;a<top;a++)
{
int temp[100]={0},toptemp=0;
int line[100]={0};
if(ans[a]==1) continue;
while(ans[a]%10!=0)
{
temp[toptemp]=ans[a]%10;
toptemp++;
ans[a]/=10;
}
for(c=0;c<100;c++)
for(d=0;d<100;d++)
{
line[c+d]+=ans2[d]*temp[c];
}
for(c=0;c<100;c++)
{
if(line[c]>=10)
{
line[c+1]=line[c+1]+line[c]/10;
line[c]=line[c]%10;
}
ans2[c]=line[c];
}
}
/*輸出答案 為7位 但是答案可能為0 所以另外做判斷*/
int flag=0;
for(a=100;a>=0;a--)
if(ans2[a]!=0)
{
for(b=a;b>=0;b--)
printf("%lld",ans2[b]);
flag=1;
printf("\n");break;
}
if(flag==0)
printf("0\n");
}
return 0;
}
上一篇:小光的煩惱[兩個油瓶]
下一篇:文文的求婚--續集 (n 行版)