C++実現L 1-006連続因子(20分)

10994 ワード

アルゴリズムの問題同前けいさんもんだい

C++実現L 1-006連続因子(20分)
一、説明
L 1-006連続因子(20分)正の整数N N Nの因子には、いくつかの連続した数字が存在する可能性がある.例えば630は3に分解できる×5×6×7、そのうち5、6、7は3つの連続した数字です.いずれかの正の整数N N N Nが与えられると、プログラムを記述して最長連続因子の個数を求め、最小連続因子シーケンスを出力する必要がある.
二、入力形式
入力は、1行に正の整数N(1三、出力フォーマット
まず1行目に最長連続因子の個数を出力する.次に、2行目において、最小の連続因子シーケンスが因子1*因子2*......*因子kのフォーマットで出力され、因子はインクリメント順に出力され、1は含まれない.
四、入力サンプル

五、出力サンプル

3
5*6*7

六、考え方

はNが素数であるか合数であるかを判断する.

素数であれば1とNそのものを直接出力する.

合数であれば、暴力的な解読方法で、要求に合致する式を見つける.

七、小知識点
1、素数判断:

bool isprime(int n)
{
   if(n==2)
       return true;
   for(int i=2;i<=sqrt(n);i++)
   {
       if(n%i==0)
           return false;
   }
   return true;
}

2、暴力の解読方法に注目する.
八、コード

#include 
#include 
#include 
using namespace std;

bool isprime(int n);
int main()
{
    int n;//     N
    cin>>n;
    if(isprime(n))
    {
        cout<<1<<endl;
        cout<<n<<endl;
    }
    else
    {
        int length=0;//    
        int i;//   for  
        int j;//   for  
        int zuixiao;//        
        for(i=2;i<=sqrt(n);i++)
        {
            if(n%i==0)
            {
                int chengji=i;//  
                int x;//    
                for(j=i+1;j<=sqrt(n);j++)
                {
                    chengji=chengji*j;
                    if(n%chengji!=0)
                        break;
                }
                if(length<j-i)
                {
                    length=j-i;
                    x=i;
                }
                zuixiao=x;
            }
        }
        cout<<length<<endl;
        for(int a=zuixiao;a<zuixiao+length;a++)
        {
            if(a!=zuixiao+length-1)
                cout<<a<<'*';
            else
                cout<<a;
        }
    }
    return 0;
}
/*    */
bool isprime(int n)
{
    if(n==2)
        return true;
    for(int i=2;i<=sqrt(n);i++)
    {
        if(n%i==0)
            return false;
    }
    return true;
}

main関数の後の呼び出し

Windows コマンド robocopy