首页利用栈的算法，质因数分解逆序输出C++

利用栈的算法，质因数分解逆序输出C++

时间: 2023-05-25 18:05:34 浏览: 106

下面是Python的实现代码： ```python def prime_factors(n): stack = [] i = 2 while i * i <= n: while n % i == 0: stack.append(i) n //= i i += 1 if n > 1: stack.append(n) res = "" while stack: res += str(stack.pop()) + " " return res.strip() n = int(input("请输入一个正整数：")) print(prime_factors(n)) ``` 解释一下算法思路：首先定义一个栈，用于保存质因子。从2开始，不断尝试除以自然数，如果能整除，则将自然数i作为一个质因子压入栈中，同时将原数除以i。如果不能整除，则i加1继续尝试。当i * i大于原数时，表示已经找到了所有的质因子。如果原数剩下的值大于1，说明剩下的这个数也是质因子之一，也需要压入栈中。最后将栈中的质因子弹出，利用字符串拼接的方式逆序输出即可。

利用栈的算法，质因数分解逆序输出（C++）

```c #include <stdio.h> #include <stdlib.h> #define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int top; } Stack; // 栈初始化 void initStack(Stack* stack) { stack->top = -1; } // 判断栈是否为空 int isEmpty(Stack stack) { return stack.top == -1; } // 入栈 void push(Stack* stack, int num) { if (stack->top == MAX_SIZE - 1) { printf("栈已满\n"); return; } stack->data[++stack->top] = num; } // 出栈 int pop(Stack* stack) { if (isEmpty(*stack)) { printf("栈为空\n"); return -1; } return stack->data[stack->top--]; } // 质因数分解 void primeFactorDecompose(int num) { Stack stack; initStack(&stack); int i; for (i = 2; i <= num; i++) { while (num % i == 0) { push(&stack, i); num /= i; } } while (!isEmpty(stack)) { printf("%d", pop(&stack)); } } int main() { int num; printf("请输入一个正整数："); scanf("%d", &num); primeFactorDecompose(num); return 0; } ```

阅读全文