Localhost8080

知行合一，自强不息

 

基于筛法的整数素因子分解

先筛出来效率会高一些

#include <iostream>   
#include <cmath>   
using namespace std;   
void findPrime(int *prime, int k, int r)    
{   
    int i;   
    for(i=0; i<r; i++)    
        prime[i]=1;   
    int j, t, s=-1,    
        u=((int)sqrt(k*1.0)-3)/2;    
    for(i=0; i<=u; i++)   
    {   
        if(prime[i])   
        { // 是素数   
            prime[++s]=t=2*i+3;   
            for(j=2*i*(i+3)+3; j<r; j+=t)    
                prime[j]=0;   
        }   
    }   
    for(; i<r; i++)   
        if(prime[i])   
            prime[++s]=2*i+3;   
    prime[s+1]=k+1; // 哨兵(用作后面的因子分解中for循环的条件判断的边界)   
}   
void solve(int n, int *prime)    
{   
    int m=2, k=(int)sqrt(n*1.0), r;   
  
    for(int t=-1; m<=k; m=prime[++t])   
    {   
        r=0;   
        for(; !(n%m); n/=m)   
            r++;   
        if(r)   
        { // r>0   
            if(r==1) // 此时n肯定不等于1，需要继续分解   
                printf("%d * ",m);   
            else  
            { // r>1   
                printf("%d^%d", m, r);   
                if(n!=1) // 需要继续分解   
                    printf(" * ");   
                else { // n==1, 分解完毕，返回   
                    printf("\n");   
                    return;   
                }   
            }    
            k=(int)sqrt(n*1.0); // r>0，说明n发生了改变(才需要重新计算k值)   
        } // if(r)   
    }   
  
    printf("%d\n",n); // 输出最后一个因子   
}    
int main()    
{   
    int m=1000000000,   
        k=(int)sqrt(m*1.0),   
        r=(k-1)/2,   
        *prime = new int[r];   
    findPrime(prime, k, r);   
    int n;   
    while(scanf("%d",&n)!=EOF)   
    {   
        printf("%d = ",n);   
        if(n==1)   
        {   
            printf("1\n");   
            continue;   
        }   
        solve(n, prime);   
    }   
    delete[] prime;   
    return 0;   
}

posted on 2010-05-27 20:47 superKiki 阅读(469) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

统计

常用链接

留言簿

随笔档案

文章分类

我的好友

一些常去的网站

搜索

最新评论

阅读排行榜

评论排行榜