程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVa 294 - Divisors

UVa 294 - Divisors

編輯:C++入門知識

UVa 294 - Divisors


計算一個給定區間中因數最多的數。

分析:數論、組合數學。題目的數據的比較大,如果暴力一定會超時,那麼就考慮利用其他方法求解。

我們將給定數字因式分解,那麼因數的個數就是π(各質因子數+1)。(每個質因子取0~上限個)

因為數據時在10^9之內,所以質因數只能是33333以內的素數,利用篩法將素數打表計算即可。

 

#include 
#include 

using namespace std;

int visit[34000];
int prime[34000];

//因式分解,計算因子個數 
int number( int a, int n )
{
	int sum = 1;
	for ( int i = 0 ; a > 1 && i < n ; ++ i ) 
		if ( a%prime[i] == 0 ) {
			int count = 1;
			while ( a%prime[i] == 0 ) {
				count ++;
				a /= prime[i];
			}
			sum *= count;
		}
	return sum;
}

int main()
{
	//利用篩法計算素數,打表 
	for ( int i = 0 ; i < 34000 ; ++ i )
		visit[i] = 1;
	int count = 0;
	for ( int i = 2 ; i < 34000 ; ++ i )
		if ( visit[i] ) {
			prime[count ++] = i;
			for ( int j = 2*i ; j < 34000 ; j += i )
				visit[j] = 0;
		}
	
	long a,b,c;
	while ( cin >> c )
	while ( c -- ) {
		cin >> a >> b;
		long save = a,max = 0,temp;
		for ( long i = a ; i <= b ; ++ i ) {
			temp = number( i, count );
			if ( temp > max ) {
				max = temp;
				save = i;
			}
		}
		
		cout << "Between " << a << " and " << b << ", " << save
			 << " has a maximum of " << max << " divisors.\n";
	}
	return 0;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved