2010年9月17日 星期五

ACM 10392 - Factoring Large Numbers

#include<stdio.h>
#include<math.h>

#define MAXSIZE 30980

int prime[MAXSIZE+1];
int prime_table[MAXSIZE],prime_table_len=0;

int makeprime(){
int i,j;

for(i=3;i<=MAXSIZE;i+=2)
if(!prime[i]){
for(j=i+i;j<=MAXSIZE;j+=i)
prime[j]=1;
prime_table[prime_table_len++]=i;
}
}

int isprime(long long int n){
int i,temp;
if(n == 2) return 0;
if(n % 2 == 0) return 2;
if(n <= MAXSIZE){
if ((1-prime[n]))
return 0;
}

for(i=0;i!=prime_table_len && prime_table[i]*prime_table[i] <= n;++i)
if(n % prime_table[i]==0)
return prime_table[i];
return 0;
}

void printFactors(long long int n)
{
long long int i;
if (n != 1 && n != 0)
i = isprime(n);
else return;
if(i)
printf("%s%lld\n", " ", i), printFactors(n/i);
if (!i && n != 1) printf("%s%lld\n", " ",n);
return;
}

int main()
{
makeprime();
long long int n, i;
while (1)
{
scanf("%lld", &n);
if (n < 0) break;
printFactors(n);
printf("\n");
}
return 0;
}


回目錄
回首頁

沒有留言 :

張貼留言

Related Posts Plugin for WordPress, Blogger...