如何快速简便的找出一个数的所有因子

C语言 码拜 6年前 (2015-05-11) 407次浏览 0个评论
 

Problem A
Quite Good Numbers
A  “perfect”  number  is  an  integer  that  is  equal  to  the  sum  of  its  divisors  (where  1  is 
considered a divisor).  For example, 6 is perfect because its divisors are 1, 2, and 3, and 1 
+ 2 + 3 is 6.  Similarly, 28 is perfect because it equals 1 + 2 + 4 + 7 + 14.
A  “quite  good”  number  is  an  integer   whose  “badness”  –  the  absolute  value  of  the 
difference between  the sum  of  its  divisors  and  the number  itself  – is  not  greater  than  a 
specified  value.    For  example,  if  the  allowable badness  is  set  at  2,  there  are  11  “quite 
good” numbers less than  100: 2, 3, 4, 6, 8, 10, 16, 20, 28, 32, and 64.  But if the allowable 
badness is set at 0 (corresponding to the “perfect” numbers) there are only 2: 6 and 28.
Your  task  is  to write  a  program  to  count  how  many  quite  good  numbers  (of  a  specified 
maximum badness) fall in a specified range.
Input
Input will  consist of specifications for a  series of tests.  Information  for each test is a single 
line containing 3 integers with a single space between items:
?
start
 (
2 <= start < 1000000)
 specifies the first number to test
?
stop
 (
start <= stop < 1000000)
 specifies the last number to test
?
badness
 (
0 <= badness < 1000)
 specifies the maximum allowable badness
A line containing 3 zeros terminates the input.
Output
Output should consist  of  one line for  each  test  comprising  the test  number  (formatted as 
shown)  followed  by  a  single  space  and  the  number  of  values  in  the  test  range  with 
badness not greater than the allowable value.
Sample Input
2 100 2
2 100 0
1000 9999 3
0 0 0
Sample Output
Test 1: 11
Test 2: 2
Test 3: 6
Australian Programming Contest
!
2013
AUPC Problem A 2013
!
page 
1
 of 
1

10分
奔跑吧,参考:

#include <math.h>
#include <stdio.h>
int sum_factor(int n)
{
	int i, sum;
	sum = 1;
	for (i = 2; i <= n / 2; i++)
	{
		if (0 == n % i) sum += i;
	}
	return sum;
}
int count(int start, int end, int badness)
{
	int i, gap, sumf, res;
	sumf = res = 0;
	for (i = start; i <= end; i++)
	{
		sumf = sum_factor(i);
		if (sumf >= i) gap = sumf - i;
		else gap = i - sumf;
		if (-badness <= gap && gap <= badness) res++;
	}
	return res;
}
int main() 
{
	int i = 1;
	int start, end, badness;
	while (scanf("%d%d%d", &start, &end, &badness))
	{
		getchar();
		if (0 == start && 0 == end && 0 == badness) break;
		printf("Test %d: %d\n", i, count(start, end, badness));
		i++;
	}
	return 0;
}
10分
应该注意到 Divisor Function(1到n中所有能整除n的整数之和)为积性函数,即对于两互质的整数p,q有f(pq) = f(p) f(q),应尽可能利用这一点,缓存f(n)的值以备将来计算f(kn)使用

代码仅供参考:

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 1000000

typedef long long LL;

LL table[MAX_N] = {0, 1};

LL sod(int n)
{
	if (table[n] != 0) return table[n];
	int p, q, c;
	for (p = 2; p < n / 2; p++)
	{
		if ( n % p == 0 ) break;
	}
	if (n % p != 0)
	{
		table[n] = 1 + n;
		return table[n];
	}
	else
	{
		int pn = p;
		LL sum = 1 + p;
		while ((q = n / pn) % p == 0)
		{
			pn *= p;
			sum += pn;
		}
		table[pn] = sum;
		table[n] = table[pn] * sod(q);
		return table[n];
	}
}

LL badness_of(int n)
{
	LL ret = sod(n) - 2 * n;
	if (ret < 0) ret = -ret;
	return ret;
}

int main(void)
{
	int start, end, badness, n = 1;
	while(scanf("%d%d%d", &start, &end, &badness) == 3)
	{
		if ((start == 0) && (end == 0) && (badness == 0))
		{
			break;
		}
		int count = 0, i;
		for (i = start; i <= end; i++)
		{
			count += badness_of(i) <= badness;
		}
		printf("Test %d: %d\n", n++, count);
	}
	return 0;
}
10分
#include<stdio.h>
#include<time.h>

unsigned int getbadness(unsigned int n)
{
	unsigned int prime_divisors[7][2]={0};	// 保存质因数及其个数,prime_divisors[i][0]为质因数,prime_divisors[i][1]为其个数
	unsigned int prime_divisors_length=0;	// ps的有效长度
	unsigned int i;
	unsigned int divisors_num=1;			// 用于计算因数个数(包括n自身)
	unsigned int sum=0;						// 用于计算因数的和
	unsigned int n_bak=n;

	// 以下为试除法求n的质因数分解
	// 试除 2
	if(!(n&1))
	{
		prime_divisors[prime_divisors_length][0]=2;
		while(!(n&1))
		{
			++prime_divisors[prime_divisors_length][1];
			n>>=1;
		}
		divisors_num*=prime_divisors[prime_divisors_length][1]+1;
		++prime_divisors_length;
	}
	// 试除 3
	if(!(n%3))
	{
		prime_divisors[prime_divisors_length][0]=3;
		while(!(n%3))
		{
			++prime_divisors[prime_divisors_length][1];
			n/=3;
		}
		divisors_num*=prime_divisors[prime_divisors_length][1]+1;
		++prime_divisors_length;
	}
	for(i=1;n>1;++i)
	{
		if((6*i-1)*(6*i-1)>n)
		{
			prime_divisors[prime_divisors_length][0]=n;
			prime_divisors[prime_divisors_length++][1]=1;
			divisors_num<<=1;
			break;
		}
		// 试除 6i-1
		if(!(n%(6*i-1)))
		{
			prime_divisors[prime_divisors_length][0]=6*i-1;
			while(!(n%prime_divisors[prime_divisors_length][0]))
			{
				++prime_divisors[prime_divisors_length][1];
				n/=prime_divisors[prime_divisors_length][0];
			}
			divisors_num*=prime_divisors[prime_divisors_length][1]+1;
			++prime_divisors_length;
		}
		// 试除 6i+1
		if(!(n%(6*i+1)))
		{
			prime_divisors[prime_divisors_length][0]=6*i+1;
			while(!(n%prime_divisors[prime_divisors_length][0]))
			{
				++prime_divisors[prime_divisors_length][1];
				n/=prime_divisors[prime_divisors_length][0];
			}
			divisors_num*=prime_divisors[prime_divisors_length][1]+1;
			++prime_divisors_length;
		}
	}

	// 以下为求除n自身以外的因数的和
	for(i=0;i<divisors_num-1;++i)
	{
		unsigned int divisor=1,j,ii=i,k;
		for(j=0;ii;ii/=prime_divisors[j++][1]+1)
		{
			k=ii%(prime_divisors[j][1]+1);
			while(k--)divisor*=prime_divisors[j][0];
		}
		sum+=divisor;
	}

	// 返回因数和与n的差的绝对值
	if(sum>n_bak)return sum-n_bak;
	else return n_bak-sum;
}

int main()
{
	unsigned int i;
	clock_t c=clock();
	for(i=2;i<1000000;++i)
		getbadness(i);
	printf("time:%lfs\n",(double)(clock()-c)/CLOCKS_PER_SEC);
	return 0;
}

时间 1.086763s 可以吗

我用最原始的方法做是超时的
10分
查表法

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明如何快速简便的找出一个数的所有因子
喜欢 (0)
[1034331897@qq.com]
分享 (0)

文章评论已关闭!