2 qq 21842183 qq_21842183 于 2016.04.17 10:47 提问

基础算法题,求思路和代码 5C

问题 E: L1-6. 连续因子
时间限制: 1 Sec 内存限制: 128 MB
题目描述
一个正整数N的因子中可能存在若干连续的数字。例如630可以分解为3*5*6*7,其中5、6、7就是3个连续的数字。给定任一正整数N,要求编写程序求出最长连续因子的个数,并输出最小的连续因子序列。

输入
输入在一行中给出一个正整数N(1<N<231)。

输出
首先在第1行输出最长连续因子的个数;然后在第2行中按“因子1*因子2*……*因子k”的格式输出最小的连续因子序列,其中因子按递增顺序输出,1不算在内。

样例输入
630
样例输出
3
5*6*7

4个回答

Meditator_hkx
Meditator_hkx   Rxr 2016.04.17 11:37

最大N应该是2^31吧?

思路比较自然的应该是:

第一步,求解输入的所有因子,并按从小到大排序;

第二步,针对因子数组,执行检查连续数操作,记录最大连续数和相应的因子数组。

当然,可能有那种边求因子边算连续数的做法,应该更省时间。我现在还没有一个这种方案的比较清晰的思路,题主加油!

cww97
cww97   2016.04.17 16:28

楼上那个,因子会有很多组的,先质因数分解,然后排出每组因子,sort

Kexiii
Kexiii   2016.04.18 12:27

最长个数显然是不超过12个的,因为12!要大于2^31,要注意对于长度为0时的素数判断
#include
#include

main()
{
unsigned long N,lenth,flag=0,start,i,power;
scanf("%lu",&N);
for(lenth = 12;lenth>=1;lenth--)
{
for(start = 2;start +lenth-1 <=sqrt(N);start++)
{
power = 1;
for(i = start;i<=start+lenth-1;i++)
{
power*=i;
}
if(N%power == 0)
{
flag=1;
break;
}
}
if(flag)
break;
}
if(lenth ==0)
{
for(i=2;i<=sqrt(N);i++)
{
if(N%i == 0)
{
printf("1\n");
printf("%d",i);
}
}
if(i >=sqrt(N))
{
printf("1\n");
printf("%d",N);
}
}
else
{
printf("%d\n",lenth);
for(i = start;i<=start+lenth-1;i++)
{
if(flag)
{
printf("%d",i);
flag=0;
}
else
printf("*%d",i);
}
}
}<


Kexiii
Kexiii   2016.04.18 12:29
 #include <math.h>
#include <stdio.h>

main()
{
    unsigned long N,lenth,flag=0,start,i,power;
    scanf("%lu",&N);
    for(lenth = 12;lenth>=1;lenth--)
    {
        for(start = 2;start +lenth-1 <=sqrt(N);start++)
        {
            power = 1;
            for(i = start;i<=start+lenth-1;i++)
            {
                power*=i;
            }
            if(N%power == 0)
            {
                flag=1;
                break;
            }
        }
        if(flag)
            break;
    }
    if(lenth ==0)
    {
        for(i=2;i<=sqrt(N);i++)
        {
            if(N%i == 0)
            {
                printf("1\n");
                printf("%d",i);
            }
        }
        if(i >=sqrt(N))
        {
                printf("1\n");
                printf("%d",N);
        }
    }
        else
        {
        printf("%d\n",lenth);
        for(i = start;i<=start+lenth-1;i++)
        {
            if(flag)
            {
                printf("%d",i);
                flag=0;
            }
            else
                printf("*%d",i);
        }
    }
}
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!