Python 利用栈质因数分解

需求

设计一个算法，利用栈实现质因数分解

例如

输入 300
输出 55322

思路

栈是大家熟知的数据结构，首先为了创建栈，需要利用python中的class：

class Stack:	
     #初始化
     def __init__(self):
         self.items = []
     #判断是否为空
     def isEmpty(self):
         return self.items == []
     #进栈
     def push(self, item):
         self.items.append(item)
     #出栈
     def pop(self):
         return self.items.pop()
 	#查看元素
     def peek(self):
         return self.items[len(self.items)-1]
 	#返回长度
     def size(self):
         return len(self.items)

其次，需要判断是否为质数：

def is_prime(x):
    if x == 2:
        return True
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True

全代码如下：

import math
class Stack:	
     #初始化
     def __init__(self):
         self.items = []
     #判断是否为空
     def isEmpty(self):
         return self.items == []
     #进栈
     def push(self, item):
         self.items.append(item)
     #出栈
     def pop(self):
         return self.items.pop()
 	#查看元素
     def peek(self):
         return self.items[len(self.items)-1]
 	#返回长度
     def size(self):
         return len(self.items)
 
def is_prime(x):
    if x == 2:
        return True
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True
    
if __name__ == '__main__':
	s1 = Stack()
	num = int(input())
	#质数进栈
	while not is_prime(num):
	    for i in range(2, int(math.sqrt(num)) + 1):
	        if (num % i == 0 and is_prime(i)):
	            s1.push(i)
	            num //= i
	            break
	s1.push(num)
	    
	while not s1.isEmpty():
	    print(s1.pop(),end='')