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;
}

回目錄
回首頁