关于n!被整除的问题【算法实现】

时间：2011-04-06 来源：冬天的草

传统的方法：

//输入：int a, n;
//输出：int i;
//算法效果：求最大的i, 使得n!(n的阶乘)可以被a^i(a的i次方)整除，而不能被a^(i+1)(a的i+1次方)整除。
#include<iostream.h>
#include<string.h>
double fac(int n);
int inline fun1(int a,int n);
//int fun2(int a,int n);
void main()
{
    int n;
    int a;
    cout<<"n=";cin>>n;
    cout<<"a=";cin>>a;

    cout<<"最大的fun1 i="<<fun1(a,n)<<endl;
}
//阶乘计算
double fac(int n)
{
    if(n==0)
        return 1;
    else
    {
        double re=1;
        for(int i=1;i<=n;i++)
        {
            re=re*i;
        }
        return re;
    }
}
int inline fun1(int a,int n)
{
    if(a==1)
        return -1;//此时最大的i为无穷大
    int p=0;
    int sum=fac(n);
    int a_p=a;

    while(1)
    {
        if((sum%(a_p))==0)
        {
            p++;
            a_p=a_p*a;
        }
        else
        {
            break;
        }
    }
    return p;
}

使用质数分解实现（非传统方法）：

//输入：int a, n;
//输出：int i;
//算法效果：求最大的i, 使得n!(n的阶乘)可以被a^i(a的i次方)整除，而不能被a^(i+1)(a的i+1次方)整除。
#include<iostream.h>

#define SIZE 100
struct PrimeItem
{
    int prime;//质数值
    int count;//质数数量
};
int* prime_factors(int n);//分解质因数
PrimeItem* GetItemArray(int n);//获取质数item链表
int Local(PrimeItem array[],int x);//元素定位
int MaxJ(int *prime,PrimeItem *arrayitem);

void main()
{
    int n,a;
    cout<<"n=";cin>>n;
    cout<<"a=";cin>>a;

    int *prime=prime_factors(a);
    PrimeItem *arrayitem=GetItemArray(n);
     cout<<"MaxJ="<<MaxJ(prime,arrayitem)<<endl;

}

//===============分解质因数================//
int* prime_factors(int n)
{
    int *array=new int[SIZE];
    int index=0;
    for(int i=2;i<=n;i++)
    {
        while(n!=i)
        {
            if(n%i==0)
            {
                array[index]=i;
                index++;
                n=n/i;
            }
            else
                break;
        }
    }

    array[index]=n;//
    index++;
    array[index]=0;//设置结束标志
    return array;
}
PrimeItem* GetItemArray(int n)
{
    PrimeItem *arraylist=new PrimeItem[SIZE];
    int *temp=new int[SIZE];
    int i,j;
    int currentindex=0;
    int find;
    for(i=0;i<SIZE;i++)
    {
        arraylist[i].count=0;
        arraylist[i].prime=0;
    }
    for(i=2;i<=n;i++)
    {
        temp=prime_factors(i);
        j=0;
        while(temp[j]!=0)
        {
            find=Local(arraylist,temp[j]);
            if(find==-1)
            {
                //没有找到
                arraylist[currentindex].prime=temp[j];
                arraylist[currentindex].count=1;
                currentindex++;
            }
            else
            {
                //该质数已经存在于质数item数组中
                //count+1
                arraylist[find].count++;
            }
            j++;
        }

    }
    return arraylist;
}
int MaxJ(int *prime,PrimeItem *arrayitem)
{
    int i;
    int count=0;
    int find;
    int condition=1;
    while(condition)
    {
        for(i=0;prime[i]!=0;i++)
        {
            find=Local(arrayitem,prime[i]);
            if(find==-1)//没有找到质数元素
            {
                break; //结束循环
            }
            else
            {
                arrayitem[find].count--;
                if(arrayitem[find].count==0)
                {
                    arrayitem[find].prime=1;//置1
                }
            }
        }
        if(prime[i]==0&&i!=0)
        {
            count++;
            //condition=1;//继续循环
        }
        else
        {
            condition=0;
        }
    }
    return count;
}
int Local(PrimeItem *array,int x)
{
    for(int i=0;array[i].prime!=0;i++)
    {
        if(array[i].prime==x)
            return i;
    }
    return -1;
}