알고리즘 노트 P167 예제: [PAT A1059] Prime Factors

알고리즘 노트 연습 문제풀이 모음집
제목 링크
제목.
Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p 1 k 1 × p 2 k 2 x ⋯ × p m k m N=p_1^{k_1}\times p_2^{k_2}x\dots\times p_m^{k_m} N=p1k1​​×p2k2​​x⋯×pmkm​​.
Input Specification:
Each input file contains one test case which gives a positive integer N N N in the range of long int.
Output Specification:
Factor N N N in the format N N N = p 1 p_1 p1​ ^ k 1 k_1 k1​ * p 2 p_2 p2​ ^ k 2 k_2 k2​ * …\dots … * p m p_m pm​ ^ k m k_m km​​​ , where p i p_i pi​'s are prime factors of N in increasing order, and the exponent k i k_i ki​​​ is the number of p i p_i pi​ – hence when there is only one p i p_i pi​​​, k i k_i ki​​​ is 1 and must NOT be printed out.
Sample Input:

97532468

Sample Output:

97532468=2^2*11*17*101*1291

사고의 방향
단계 3과 단계 4는 질인자 분해 함수primeFactorization로 통합되어 코드를 구체적으로 실현한다.

개소수표는 231\sqrt{2^{31}}231보다 약간 크다고 판단하면 된다.

왜냐하면2× 3 × 5 × 7 × 11 × 13 × 17 × 19 × 23 > 2 31 − 1 2\times3\times5\times7\times11\times13\times17\times19\times23>2^{31}-1 2×3×5×7×11×13×17×19×23>231 -3.1 따라서 인수분해 결과를 통계한 수조는 10까지 열면 되고 수조factors[10]를 열어 초기화한다.

누적소수표primeTable, num에 대해 인식 분해를 하고 n = num:a. 누적primeTable[i] > sqrt(num)시 누적하는 것을 정지한다.b. primeTable[i]를 정제할 수 있다면n 이 소수의 값을 factors[i].x에 기록한다.c. 끊임없이 primeTable[i]로 제거n를 하고 제거할 수 없을 때까지 동시에 제거의 횟수를 통계하고 기록factors[i].exp한다.

반복이 끝난 후n == 1 인식분해가 완료된 경우 sqrt(num)보다 큰 인자가 남아 정보를 기록factors한다.

factors에 따라 답안을 출력한다.

세부 사항:

factors는 왜 10가 아닌 9를 열었습니까?단계 4의 큰 인자에 위치를 남겨야 하기 때문이다.

특판 입력1이 필요한 경우;

정식으로 인식 분해를 진행하는 부분은 num에 직접 손을 댈 수 없으며 사본을 남겨야 한다.

대수조는 전역 변수로 만들어야 하며 main나 다른 함수에 열 수 없습니다. 그렇지 않으면 세그먼트 오류가 발생합니다.

코드

#include 
#include  

#define MAX 50000

typedef struct {
	int x, exp;
} Factor; 

//      
int isPrime[MAX], primeCnt = 0, primeTable[MAX/10];
int findPrime(void) {
	int i, j;
	for (i = 2; i < MAX; ++i)
		isPrime[i] = 1;
	for (i = 2; i < MAX; ++i) {
		if (isPrime[i]) {
			primeTable[primeCnt++] = i; 
			for (j = i; j < MAX; j += i)
				isPrime[j] = 0; 
		} 
	} 
} 

//   num      ，     factors，        
//    num >= 2 
int primeFactorization(int num, Factor *factors) {
	int i, n = num;		// n   num     
	int factorCnt = 0;
	for (i = 0; i < 10; ++i)
		factors[i].exp = 0;
	for (i = 0; i < primeCnt; ++i) {
		if ((int)sqrt((double)num) < primeTable[i])
			break;
		if (n % primeTable[i] == 0) {
			factors[factorCnt].x = primeTable[i];
			while (n % primeTable[i] == 0) {
				n /= primeTable[i];
				++factors[factorCnt].exp;
			}
			++factorCnt;
		}
	}
	if (n != 1) {
		factors[factorCnt].x = n;
		factors[factorCnt].exp = 1;
		++factorCnt;
	}
	return factorCnt;
} 

int main() {
	findPrime();		//    
	int num, i;
	scanf("%d", &num);
	if (num == 1) {		//    
		printf("1=1");
		return 0;
	}
	//       
	Factor factors[10];
	int factorCnt = primeFactorization(num, factors);
	//    
	int flag = 0;
	printf("%d=", num); 
	for (i = 0; i < factorCnt; ++i) {
		if (flag)
			putchar('*');
		flag = 1;
		printf("%d", factors[i].x);
		if (factors[i].exp > 1) 
			printf("^%d", factors[i].exp); 
	} 
	return 0;
}