컴퓨터 알고리즘 설계 및 분석 교과서(왕효동 저) 수업 후 알고리즘 실현 문제 1-3 최대 약수 문제

문제 설명: 정수 x의 약수는 x를 정제할 수 있는 정수입니다.양의 정수 x의 약수 개수는 div(x)로 기록됩니다.예를 들어 12510은 모두 10의 약수이고 div(10)=4이다.a와 b는 두 개의 정수이고 a<=b를 설정하여 a와 b 사이에 가장 많은 수의 x를 찾아낸다.알고리즘 설계: 주어진 두 개의 정수 a<=b에 대해 a와 b 사이의 약수 개수가 가장 많은 수를 계산한다.데이터의 입력과 출력: 입력 파일 예시 출력 파일 예시 1 369 문제 분석: 폭력적인 해답을 구하는 방법으로 수의 약수를 직접 구할 수 있는 개수, 시간 복잡도는 O(n)이고 수의 증가에 따라 시간 복잡도도 커지기 때문에 적합하지 않다. 여기서 약수 개수의 정리를 사용할 수 있다. n분해질 인수 n=p1^a1*p2^a2*p3^a3.pk^ak는 n의 약수의 개수가 (a2+1)(ak+1)...(ak+1),(ak+1),(ak+1)질량 인수를 구하는 과정에서 숫자가 끊임없이 줄어들고 시간의 복잡도는 O(logN)이다.

/*****************************************************************
source:       1-3
mean of the title:       ，               
          
  2.0:      ，n      n=p1^a1*p2^a2*p3^a3*…*pk^ak
 ，n        (a1+1)(a2+1)(a3+1)…(ak+1)
*****************************************************************/

#include
#include
#include
using namespace std;

int prime_num[10000];//         

int isprime(int n){//  n      
	bool flag = true;
	for (int i = 2; i <= sqrt(n); i++){
		if (n%i == 0){
			flag = false;
			break;
		}
	}
	return flag;
}

int solve(int n){// n      
	memset(prime_num, 0, sizeof(prime_num));
	int count = 1;
	int num = n;
	if (num == 1)
		return 1;
	if (isprime(num))
		return 2;
	for (int i = 2; i <= sqrt(num); i++){//      
		if (!(n%i)){
			prime_num[i]++;
			n /= i;
			i--;//  i，        
		}
	}
	for (int i = 2; i <= num; i++){
		if (prime_num[i]){
			//cout<> a >> b;

	for (int i = a; i <= b; i++){
		if (solve(i)>max){
			max = solve(i);
		}
	}
	cout << "The largest number of divisor is " << max << endl;
	return 0;
}

폭력 해답 코드

#include
#include
using namespace std;
int main(){
	int a,b;
	int number,max=0;
	cout<>a>>b;
	
	for(int i=a;i<=b;i++){
		number=0;
		for(int j=1;j<=sqrt(i);j++){
			if(!(i%j)){
				if(j!=(i/j))
					number+=2;
				else
					number+=1;
			}
				
		}
		if(number>max)
			max=number;
	}
	
	cout<

약수 개수의 정리가 증명된 일부 개인적인 사고방식에 대한 가설 n=2^n13^n3을 추가하면 n1개는 2곱하기 n2개는 3이고 n1개는 n2개2에서 2를 취하면 n2개의 3에서 2를 곱하기 (n2+1)개와 3을 곱하기 때문에 한 번 곱할 때마다 원수가 두 개 더 많아진다. n1개의 2에서 2를 취하면 n2개의 3에서 2를 취하기 (n2+1)개와 2개의 2를 곱하면 원수가 더 많아진다.그러면 n1개 2로 확장, 0개 2를 뽑을 때 36이 n1개 2에서 모두 (n1+1) 개 2(0개 2를 뽑을 때 1과 원수를 곱하기)를 뽑기 때문에 원수는 모두 2*(n1+1)*(n2+1)*(n2+1)가 있고, 중복이 있기 때문에 마지막에 2로 나누어야 한다.