0

我想找到任何数字的总因子。在数论中，因式分解是将合数分解为更小的非平凡除数，当它们相乘时等于原始整数。你的工作是计算一个数字的唯一分解数（至少包含两个大于一的正整数）。

例如：12 有 3 个独特的因式分解： 2*2*3, 2*6, 3*4 。注意：3*4 和 4*3 不认为是不同的。

我试图找到这一点，但并没有完全准确。这是我的代码：

#include<iostream>
using namespace std;
int count=0;
void factor(int n,int c,int n1)
{
    for(int i=n1; i<n ; i++)
    {
        if(c*i==n)
            {count++;
            return;}
        else
        if(c*i>n)
            return;
        else
        factor(n,c*i,i+1);
    }
    return;
}
int main()
{
    int num,n;
    cin>>num;
    for(int i=0 ; i<num ; i++)
    {
        cin>>n;
        count=0;
        factor(n,1,1);
        cout<<count<<endl;
    }
    return 0;
}

输入是测试用例的数量，后跟测试用例（数字）。

示例：输入：3 12 36 3150

输出：3 8 91

4

3 回答 3

2

我认为您正在寻找一个数字的独特分解数。为此，我认为您需要找到该数字的素数的数量。说为

12 = 2, 2, 3

总计数 = 3；对于 2、2、3，我们需要

(2*2)*3  ~ 4*3
2*(2*3)  ~ 2*6
2*2*3    ~ 2*2*3

为了解决这个问题，我们在 Grimaldi、离散和组合数学中找到了想法。要找到添加到数字（n）的方法数是 2^(n-1) -1。对于 3，我们有...

3 =
1+1+1
2+1
1+2

总计数 = 2^(3-1) -1 = 4-1 = 3

我们可以类比来看

1+1+1 is equivalent to 2*2*3
1+2 is equivalent to 2*(2*3)
2+1 is equivalent to (2*2)*3

Say number of prime factors = n
So we have number of factorizations = 2^(n-1)-1

编码：

#include <stdio.h>
int power(int x, int y)
{
    int prod =1, i ;
    for(i=1; i<=y;i++) prod *= x;
    return prod;
}

int main()
{
    int number,div;    
    int count  = 0, ti, t;
    printf("Input: ");    
    scanf("%d",&t);
    for(ti=1; ti<=t;ti++)
    { 
        scanf("%d", &number);
        div = 2;count = 0;
        while(number != 0)
        {
            if(number%div!=0) div = div + 1;            
            else 
            {
                number = number / div;
                //printf("%d ",div);
                count++;
                if(number==1) break;
            }
        }
        printf("%d ", power(2,count-1)-1);
    }
    return 0;
}
于 2013-11-13T04:14:58.453 回答
1

Usingmod在尝试考虑以下因素时非常有用：

for(int i = 1; i <= fnum; ++i){ //where fnum is the number you wish to factor
    if(!(fnum % i)) ++count;
}
return count;

交叉这个是因子数，不是唯一因子，如果你想要唯一因子的数量，你必须做一些额外的工作。

于 2013-11-13T03:57:43.200 回答
0

解决方案是实现所有排列中，恰好有一个是排序的。2 * 4 * 7 * 3给出与 相同的结果2 * 3 * 4 * 7。这意味着当您找到一个因素时，您不应该检查其余因素是否存在较低的因素。但是，您应该检查是否再次出现相同的因素：12 = 2 * 2 * 3。序列2 2 3也被排序。

顺便说一句，你应该给你的变量更清晰的名字，或者至少添加一些描述它们的注释。

于 2013-11-13T12:22:11.973 回答