Question

c语言求质因子（质数且是输入数的因子）最多的那个数

n<10^9;时间复杂度在10^8内，谢谢大神来看题
输入n，求1~n中质因子最多的那个数

Answer 1

要找到满足题意的数，

就是小于等于n的最大的2的幂，

证明：

假设这个数m是2^k，并且2^k小于等于n。

那么它有k个质因子（都是2），

反证法：

假如某个数x有k+1个因子，

质数里面最小的是2，那么该数x一定满足：

m<2^(k+1)<=x<=n

因为m是小于等于n的最大的2的幂，因此x不存在。

所以m就是小于等于n的最大的2的幂。

(注意这里说的是最多有k个因子，最小的是2^k,k个因子还可能是2^(k-1)*3，也是有可能的，但是就是不可能有k+1个因子)

代码：

#include <stdio.h>
unsigned flp2(unsigned x)
{
	x = x | (x >> 1);
	x = x | (x >> 2);
	x = x | (x >> 4);
	x = x | (x >> 8);
	x = x | (x >> 16);
	return x - (x >> 1);
}
int main()
{
	printf("%u", flp2(1000000000));
	return 0;
}

追问

额，看不懂。。。。能换一种表达方式吗？

追答

就是说，满足条件的最小的那个数，一定是
2*2*2...这种形式，
就是2的幂。