请教：怎样求一个正整数的全部奇数约数？

ithiker 2010-01-31 11:18:14
对任意一个数，求它的除1外的奇数约数。比如，135，它的全部奇数约数（1除外）为：3，5，9，15，27，45，135。
我编了一个程序，思路是这样的：
1.首先求出它的全部奇数因子，比如135的为3，3，3，5
2.用这些因子两两，三三，四四……相乘得出奇数约数
第一步的思路比较清楚，第二步算的时候写循环比较繁复，并且输出为：
3 3 3 5 9 9 15 9 15 15 27 45 135
Process returned 0 (0x0) execution time : 0.156 s
重复好多

大家帮我看看，第二步能不能优化下。或者这个问题本身还有没有其它更好的方法，多些各位。
下面是我的代码：


#include<vector>

#include<iostream>

using namespace std;

vector<long>Factorization (long  M)

{

    vector<long> ret;

    long k, mul;

    vector<long>::size_type i, j, t, n, step;

    for (k = 2; k <= M; k++)

    {

        if (M % k == 0)

        {

            M = M / k;

            if (k % 2 != 0)

                ret.push_back (k);

            k = 2;

        }

    }

    n = ret.size();

    if (n != 0)

    {

        for (step = 1; step <= n - 1; step++)//这往下，感觉复杂罗嗦，但又不知道怎么改

        {

            for (i = 0; i < n - step; i ++)

            {

                for (j = i + step; j <= n - 1; j = j + step)

                {

                    mul = ret[i];

                    for (t = j - step + 1; t <= j; t++)

                        mul *= ret[t];

                    ret.push_back (mul);

                }

            }

        }

    }

    for (i = 0; i < ret.size(); i ++)

        cout << ret[i] << "  ";

    return ret;

}



int main()

{

    Factorization(135);



    return 0;

}

...全文
1615 29 打赏 收藏 转发到动态 举报
写回复
用AI写文章
29 条回复
切换为时间正序
请发表友善的回复…
发表回复
ithiker 2010-02-02
  • 打赏
  • 举报
 回复
[Quote=引用 28 楼 febbird1984 的回复:]
虽然结贴了,还是想贴下改进后的算法

假设M为任意整数,那么可以有M=a*b,a和b为正整数,假定a <=b的话,那么可以知道1 <=a <=M^(1/2) <=b <=M
假设已知a,那么可以知道(M/a,M)区间上的数肯定不符合条件,所以可以将该区间的数去掉
如果M mod a=0,那么a和b都是M的因数,分别判断奇偶,奇数是符合条件的
增加a的值至a',去掉(M/a',M/a)中间的数
    这里M为偶数的话,每次增加1;M为奇数的话,每次增加2.因为偶数*偶数=偶数,偶数*奇数=偶数,奇数*奇数=奇数
如此循环,直到a>=M/a;
可以将复杂度降低到O(n^0.5)
这样要判断的数的数目大致为M^0.5 / ((M mod 2)+1)


vector <unsigned long>Factorization (unsigned long  M)

{

vector <unsigned long> ret;

unsigned long a=2,b=M;

unsigned char step;



if (M%a==0)

{

step=1;

}

else

{

step=2;

ret.push_back(M);

}



for(a=3;a <b;a+=step)

{

b=M/a;

if(M%a==0)

{

if(a%2==1)

{

ret.push_back(a);

}



if(b%2==1)

{

ret.push_back(b);

}

}

}

for (unsigned int i = 0; i < ret.size(); i ++)

        cout < < ret[i] < < "  ";

    return ret;

}

int main()

{

Factorization(1000000000);

return 0;

}


[/Quote]

谢谢，学习了
mstlq 2010-02-01
  • 打赏
  • 举报
 回复
[Quote=引用 25 楼 gigglesun 的回复:]
引用 20 楼 mstlq 的回复:
稍微弄短点……
C/C++ code所有奇约数是：525125625312515625781253906251953125
Process returned0 (0x0)  execution time :0.016 s
Press any key tocontinue.
C/C++ code
#include <iostream>
#include <string>usingnamespace std;
unsignedint priDivs[32];
unsignedint divCnts[32];
unsignedint divC;void init()
{
    memset(priDivs,0,32*sizeof(unsignedint));
    memset(divCnts,0,32*sizeof(unsignedint));
    divC=0;
};void getPriDivs(unsignedint n)
{while(n%2==0) n/=2;for(unsignedint i=3; i <=n;++i) {if(n%i==0)++divC;while(n%i==0) {
            priDivs[divC-1]=i;++divCnts[divC-1];
            n/=i;
        }
    }return ;
};void showOddDivs(unsignedint pro,unsignedint dep)
{if(dep==divC)
            (pro==1)? (cout < <"所有奇约数是：\n") : (cout < <pro < <'\t');elsefor(unsignedint i=0;i <=divCnts[dep];++i,pro*=priDivs[dep])
            showOddDivs(pro,dep+1);return;
}void Factorization(unsignedint n)
{
    init();
    getPriDivs(n);
    showOddDivs(1,0);return ;
}int main()
{
    Factorization(1000000000);return0;
}

这个放我的Codeblocks上居然提示： 'memset' was not declared in this scope；
放别的上面运行好使，再次感谢，时候不早了，睡觉~
[/Quote]

#include<cstring>
ithiker 2010-02-01
  • 打赏
  • 举报
 回复
[Quote=引用 20 楼 mstlq 的回复:]
稍微弄短点……
C/C++ code所有奇约数是：525125625312515625781253906251953125
Process returned0 (0x0) execution time :0.016 s
Press any key tocontinue.
C/C++ code
#include<iostream>
#include<string>usingnamespace std;
unsignedint priDivs[32];
unsignedint divCnts[32];
unsignedint divC;void init()
{
memset(priDivs,0,32*sizeof(unsignedint));
memset(divCnts,0,32*sizeof(unsignedint));
divC=0;
};void getPriDivs(unsignedint n)
{while(n%2==0) n/=2;for(unsignedint i=3; i<=n;++i) {if(n%i==0)++divC;while(n%i==0) {
priDivs[divC-1]=i;++divCnts[divC-1];
n/=i;
}
}return ;
};void showOddDivs(unsignedint pro,unsignedint dep)
{if(dep==divC)
(pro==1)? (cout<<"所有奇约数是：\n") : (cout<<pro<<'\t');elsefor(unsignedint i=0;i<=divCnts[dep];++i,pro*=priDivs[dep])
showOddDivs(pro,dep+1);return;
}void Factorization(unsignedint n)
{
init();
getPriDivs(n);
showOddDivs(1,0);return ;
}int main()
{
Factorization(1000000000);return0;
}
[/Quote]
这个放我的Codeblocks上居然提示： 'memset' was not declared in this scope；
放别的上面运行好使，再次感谢，时候不早了，睡觉~
ithiker 2010-02-01
  • 打赏
  • 举报
 回复
[Quote=引用 12 楼 traceless 的回复:]
如果按照LZ你的思路来，

LZ 你的第一步都错了，如果第一步恰当的话，第二步只用两个循环即可
[/Quote]

没写清楚，不好意思，应该是第一步求奇数素数因子
lovesi3344 2010-02-01
  • 打赏
  • 举报
 回复
他对得起几个星星和几个勋章
！！！

[Quote=引用 22 楼 gigglesun 的回复:]
楼上真强大，这么快就写好了，佩服佩服，多谢多谢
[/Quote]
ithiker 2010-02-01
  • 打赏
  • 举报
 回复
楼上真强大，这么快就写好了，佩服佩服，多谢多谢
mstlq 2010-02-01
  • 打赏
  • 举报
 回复
按7楼的提示
getPriDivs有一个更好的实现方法……


void getPriDivs(unsigned int n)

{

    --divC;

    while(n%2==0) n/=2;

    for(unsigned int i=3; i<=n; i+=2) {

        if(n%i==0) ++divC;

        while(n%i==0) {

            priDivs[divC]=i;

            ++divCnts[divC];

            n/=i;

        }

    }

    ++divC;

    return ;

};

mstlq 2010-02-01
  • 打赏
  • 举报
 回复
稍微弄短点……
所有奇约数是：

5       25      125     625     3125    15625   78125   390625  1953125

Process returned 0 (0x0)   execution time : 0.016 s

Press any key to continue.







#include <iostream>

#include <string>

using namespace std;

unsigned int priDivs[32];

unsigned int divCnts[32];

unsigned int divC;



void init()

{

    memset(priDivs,0,32*sizeof(unsigned int));

    memset(divCnts,0,32*sizeof(unsigned int));

    divC=0;

};

void getPriDivs(unsigned int n)

{

    while(n%2==0) n/=2;

    for(unsigned int i=3; i<=n; ++i) {

        if(n%i==0) ++divC;

        while(n%i==0) {

            priDivs[divC-1]=i;

            ++divCnts[divC-1];

            n/=i;

        }

    }

    return ;

};



void showOddDivs(unsigned int pro,unsigned int dep)

{

    if(dep==divC)

            (pro==1)? (cout<<"所有奇约数是：\n") : (cout<<pro<<'\t');

    else

        for(unsigned int i=0;i<=divCnts[dep];++i,pro*=priDivs[dep])

            showOddDivs(pro,dep+1);

    return;

}

void Factorization(unsigned int n)

{

    init();

    getPriDivs(n);

    showOddDivs(1,0);

    return ;

}

int main()

{

    Factorization(1000000000);

    return 0;

}
mstlq 2010-02-01
  • 打赏
  • 举报
 回复
计算 10^9的代码……
5       25      125     625     3125    15625   78125   390625  1953125

Process returned 0 (0x0)   execution time : 0.031 s

Press any key to continue.








#include <iostream>

#include <string>

using namespace std;

unsigned int priDivs[32];

unsigned int divCnts[32];

unsigned int divC;



void init()

{

    memset(priDivs,0,32*sizeof(unsigned int));

    memset(divCnts,0,32*sizeof(unsigned int));

    divC=0;

};

void getPriDivs(unsigned int n)

{

    bool cinc=false;

    while(n%2==0) n/=2;

    for(unsigned int i=3; i<=n; ++i) {

        cinc=false;

        while(n%i==0) {

            cinc=true;

            priDivs[divC]=i;

            ++divCnts[divC];

            n/=i;

        }

        if (cinc) ++divC;

    }

    return ;

};



void showOddDivs(unsigned int pro,unsigned int dep)

{

    if(dep==divC){

        if (pro!=1)

            cout<<pro<<"\t";

    }

    else {

        for(unsigned int i=0;i<=divCnts[dep];++i)

        {

            showOddDivs(pro,dep+1);

            pro*=priDivs[dep];

        }

    }

    return;

}

void Factorization(unsigned int n)

{



    init();

    getPriDivs(n);

    showOddDivs(1,0);

    return ;

}

int main()

{

    Factorization(1000000000);



    return 0;

}
febbird1984 2010-02-01
  • 打赏
  • 举报
 回复
有一个问题,10^9对于long来说应该溢出了
febbird1984 2010-02-01
  • 打赏
  • 举报
 回复
虽然结贴了,还是想贴下改进后的算法

假设M为任意整数,那么可以有M=a*b,a和b为正整数,假定a<=b的话,那么可以知道1<=a<=M^(1/2)<=b<=M
假设已知a,那么可以知道(M/a,M)区间上的数肯定不符合条件,所以可以将该区间的数去掉
如果M mod a=0,那么a和b都是M的因数,分别判断奇偶,奇数是符合条件的
增加a的值至a',去掉(M/a',M/a)中间的数
这里M为偶数的话,每次增加1;M为奇数的话,每次增加2.因为偶数*偶数=偶数,偶数*奇数=偶数,奇数*奇数=奇数
如此循环,直到a>=M/a;
可以将复杂度降低到O(n^0.5)
这样要判断的数的数目大致为M^0.5 / ((M mod 2)+1)


vector<unsigned long>Factorization (unsigned long  M)

{

	vector<unsigned long> ret;

	unsigned long a=2,b=M;

	unsigned char step;



	if (M%a==0)

	{

		step=1;

	}

	else

	{

		step=2;

		ret.push_back(M);

	}

	

	for(a=3;a<b;a+=step)

	{

		b=M/a;

		if(M%a==0)

		{

			if(a%2==1)

			{

				ret.push_back(a);

			}

			

			if(b%2==1)

			{

				ret.push_back(b);

			}

		}

	}

	for (unsigned int i = 0; i < ret.size(); i ++)

        cout << ret[i] << "  ";

    return ret;

}

int main() 

{ 

	Factorization(1000000000);

	return 0;

}

wodespace 2010-02-01
  • 打赏
  • 举报
 回复
呵呵，虽然暑假参加过程序设计大赛，但我主要学的是java
所以算法问题还是多看看数据结构，不好意思哦
加油哦！
febbird1984 2010-01-31
  • 打赏
  • 举报
 回复
穷举法计算10^9的话我机子上大概3秒钟,还是可以接受的
mstlq 2010-01-31
  • 打赏
  • 举报
 回复
想10^9也保持高速？
也是可以的……

先吃个宵夜，回来洗个澡，然后开始写……

买啤酒去……
windsting 2010-01-31
  • 打赏
  • 举报
 回复
[Quote=引用 13 楼 lovesi3344 的回复:]
整除规则第一条（1）：任何数都能被1整除。
整除规则第二条（2）：个位上是2、4、6、8、0的数都能被2整除。
整除规则第三条（3）：每一位上数字之和能被3整除，那么这个数就能被3整除。
整除规则第四条（4）：最后两位能被4整除的数，这个数就能被4整除。
整除规则第五条（5）：个位上是0或5的数都能被5整除。
整除规则第六条（6）：一个数只要能同时被2和3整除，那么这个数就能被6整除。
整除规则第七条（7）：把个位数字截去，再从余下的数中，减去个位数的2倍，差是7的倍数，则原数能被7整除。
整除规则第八条（8）：最后三位能被8整除的数，这个数就能被8整除。
整除规则第九条（9）：每一位上数字之和能被9整除，那么这个数就能被9整除。
整除规则第十条（10）： 若一个整数的末位是0，则这个数能被10整除
整除规则第十一条（11）：若一个整数的奇位数字之和与偶位数字之和的差能被11整除，则这个数能被11整除。11的倍数检验法也可用上述检查7的「割尾法」处理！过程唯一不同的是：倍数不是2而是1！
整除规则第十二条（12）：若一个整数能被3和4整除，则这个数能被12整除。
整除规则第十三条（13）：若一个整数的个位数字截去，再从余下的数中，加上个位数的4倍，如果差是13的倍数，则原数能被13整除。如果差太大或心算不易看出是否13的倍数，就需要继续上述「截尾、倍大、相加、验差」的过程，直到能清楚判断为止。
整除规则第十四条（14）：a 若一个整数的个位数字截去，再从余下的数中，减去个位数的5倍，如果差是17的倍数，则原数能被17整除。如果差太大或心算不易看出是否17的倍数，就需要继续上述「截尾、倍大、相减、验差」的过程，直到能清楚判断为止。b 若一个整数的末三位与3倍的前面的隔出数的差能被17整除，则这个数能被17整除。
整除规则第十五条（15)：a 若一个整数的个位数字截去，再从余下的数中，加上个位数的2倍，如果差是19的倍数，则原数能被19整除。如果差太大或心算不易看出是否19的倍数，就需要继续上述「截尾、倍大、相加、验差」的过程，直到能清楚判断为止。b 若一个整数的末三位与7倍的前面的隔出数的差能被19整除，则这个数能被19整除。
整除规则第十六条（16）：若一个整数的末四位与前面5倍的隔出数的差能被23整除，则这个数能被23整除
整除规则第十七条（17）：若一个整数的末四位与前面5倍的隔出数的差能被2)整除，则这个数能被29整除
[/Quote]
我觉得这个不是很实际，因为不出意外的话接下来的“整除规则第十八条（18）”应该就是关于“什么样的数字可以被31整除”，这样下去这个规则几乎是没有止境的，应用起来也不具有操作性，我觉得像这样的“大量重复劳动”就用该让电脑去穷举，并且这个方法的复杂度应该是O(n)[其实只需要n/2就可以了]，是一个非常可以接受的方案，至于你的这些规则，其实是给人类用双眼判断的时候“偷懒”用的。
ithiker 2010-01-31
  • 打赏
  • 举报
 回复
3L的不可以做偶数
lovesi3344 2010-01-31
  • 打赏
  • 举报
 回复
整除规则第一条（1）：任何数都能被1整除。
整除规则第二条（2）：个位上是2、4、6、8、0的数都能被2整除。
整除规则第三条（3）：每一位上数字之和能被3整除，那么这个数就能被3整除。
整除规则第四条（4）：最后两位能被4整除的数，这个数就能被4整除。
整除规则第五条（5）：个位上是0或5的数都能被5整除。
整除规则第六条（6）：一个数只要能同时被2和3整除，那么这个数就能被6整除。
整除规则第七条（7）：把个位数字截去，再从余下的数中，减去个位数的2倍，差是7的倍数，则原数能被7整除。
整除规则第八条（8）：最后三位能被8整除的数，这个数就能被8整除。
整除规则第九条（9）：每一位上数字之和能被9整除，那么这个数就能被9整除。
整除规则第十条（10）： 若一个整数的末位是0，则这个数能被10整除
整除规则第十一条（11）：若一个整数的奇位数字之和与偶位数字之和的差能被11整除，则这个数能被11整除。11的倍数检验法也可用上述检查7的「割尾法」处理！过程唯一不同的是：倍数不是2而是1！
整除规则第十二条（12）：若一个整数能被3和4整除，则这个数能被12整除。
整除规则第十三条（13）：若一个整数的个位数字截去，再从余下的数中，加上个位数的4倍，如果差是13的倍数，则原数能被13整除。如果差太大或心算不易看出是否13的倍数，就需要继续上述「截尾、倍大、相加、验差」的过程，直到能清楚判断为止。
整除规则第十四条（14）：a 若一个整数的个位数字截去，再从余下的数中，减去个位数的5倍，如果差是17的倍数，则原数能被17整除。如果差太大或心算不易看出是否17的倍数，就需要继续上述「截尾、倍大、相减、验差」的过程，直到能清楚判断为止。b 若一个整数的末三位与3倍的前面的隔出数的差能被17整除，则这个数能被17整除。
整除规则第十五条（15)：a 若一个整数的个位数字截去，再从余下的数中，加上个位数的2倍，如果差是19的倍数，则原数能被19整除。如果差太大或心算不易看出是否19的倍数，就需要继续上述「截尾、倍大、相加、验差」的过程，直到能清楚判断为止。b 若一个整数的末三位与7倍的前面的隔出数的差能被19整除，则这个数能被19整除。
整除规则第十六条（16）：若一个整数的末四位与前面5倍的隔出数的差能被23整除，则这个数能被23整除
整除规则第十七条（17）：若一个整数的末四位与前面5倍的隔出数的差能被2)整除，则这个数能被29整除
traceless 2010-01-31
  • 打赏
  • 举报
 回复
如果按照LZ你的思路来，

LZ 你的第一步都错了，如果第一步恰当的话，第二步只用两个循环即可
JQL2010 2010-01-31
  • 打赏
  • 举报
 回复
不用包括本身么
febbird1984 2010-01-31
  • 打赏
  • 举报
 回复
穷举法的花的时间比找合数的因子花的时间还要短
所以,不要想那么复杂的算法了
加载更多回复（9）
求两个正整数的最大公约数
他使用暴力枚举的方法，试图寻找到一个合适的整数 i，看看这个整数能否被两个整型参数numberA和numberB同时整除。这个整数 i 从2开始循环累加，一直累加到 numberA 和 numberB 中较小参数的一半为止。循环结束后，.....
求最大公约数（四种算法）
辗转相除法（又名欧几里德法）C语言中用于计算两个正整数a,b的最大公约数和最小公倍数，实质它依赖于下面的定理： 其算法过程为： 前提：设两数为a,b设其中a 做被除数,b做除数，temp为余数 （1）、大数放a中、小数...
C语言求两数最大公约数的四种算法
实验目的 1.明确算法的概念和特点； 2.通过对问题的分析，设计合理的算法解决问题。 实验内容 ...将每一种算法用一个函数实现，再在主函数中用switch()语句调用任意一种算法，并且在主函数中利用ra...
用辗转相除法，穷举法，更相减损法，stein求两个数的最大公约数，并比较时间。
题目分析 用四种不同的方法求两个数的最大公约数 辗转相除法： 其算法过程为：前提：设两数为a,b设其中a 做被除数,b做除数，temp为余数 ...穷举法（也叫枚举法）穷举法求两个正整数的最大公约数的解题步骤：从...
运行最大公约数的常用算法，并比较其运行时间
辗转相除法（又名欧几里德法）C语言中用于计算两个正整数a,b的最大公约数和最小公倍数。 ①函数嵌套调用 其算法过程为：前提：设两数为a,b设其中a 做被除数,b做除数，temp为余数 1、大数放a中、小数放b中； 2、....
C++ 语言

64,683

社区成员

250,490

社区内容

发帖
与我相关
我的任务
社区描述
C++ 语言相关问题讨论，技术干货分享，前沿动态等
c++ 技术论坛（原bbs）
社区管理员
  • C++ 语言社区
  • encoderlee
  • paschen
加入社区
  • 近7日
  • 近30日
  • 至今

加载中

查看更多榜单
社区公告
  1. 请不要发布与C++技术无关的贴子
  2. 请不要发布与技术无关的招聘、广告的帖子
  3. 请尽可能的描述清楚你的问题，如果涉及到代码请尽可能的格式化一下

试试用AI创作助手写篇文章吧

+ 用AI写文章