质数因子求解

目录

一、什么是质数因子

二、对3233的求解过程

1.先编写代码判断哪个是质数

2.再循环判断每一个质数进行判断

3.加大难度、计算53841

4.优化代码

三、极端情况

---

一、什么是质数因子

二、对3233的求解过程

1.先编写代码判断哪个是质数

# 判断一个数是否为质数
def is_prime(n):
    # for i in range(2, n):
    # for i in range(2, n//2+1):
    # for i in range(3, n//2+1, 2):
    loop = int(math.sqrt(n))+1  # 任何一个数，其因子只需要找小于其开根号的整数即可，
    for i in range(2, loop):
        if n % i == 0:
            return False
    return True
 
 
# 给定一个数，求其乘积因子，并确保一定是质数
def prime_pq(n):
    start = time.time()
    for p in range(1, n):
        for q in range(1, n):
            # 如果找到因子且两个因子均为质数，则可以直接得出结论，不需要继续循环
            if p * q == n and is_prime(p) and is_prime(q):
                print(p, q)
                end = time.time()
                print(end-start)
                exit(0)

2.再循环判断每一个质数进行判断

def prime_pq(n):
    start = time.time()
    for p in range(1, n):
        for q in range(1, n):
            # 如果找到因子且两个因子均为质数，则可以直接得出结论，不需要继续循环
            if p * q == n and is_prime(p) and is_prime(q):
                print(p, q)
                end = time.time()
                print(end-start)
                exit(0)

3.加大难度、计算53841

4.优化代码

# 质数因子求解
import time, math
 
# 判断一个数是否为质数
def is_prime(n):
    # for i in range(2, n):
    # for i in range(2, n//2+1):
    # for i in range(3, n//2+1, 2):
    loop = int(math.sqrt(n))+1  # 任何一个数，其因子只需要找小于其开根号的整数即可，
    for i in range(2, loop):
        if n % i == 0:
            return False
    return True
 
 
# 给定一个数，求其乘积因子，并确保一定是质数
def prime_pq(n):
    start = time.time()
    for p in range(1, n):
        for q in range(1, n):
            # 如果找到因子且两个因子均为质数，则可以直接得出结论，不需要继续循环
            if p * q == n and is_prime(p) and is_prime(q):
                print(p, q)
                end = time.time()
                print(end-start)
                exit(0)
 
 
# 第一轮算法优化：p和q的循环次数减半
def prime_01(n):
    start = time.time()
    for p in range(1, n//2+1):
        for q in range(1, n//2+1):
            # 如果找到因子且两个因子均为质数，则可以直接得出结论，不需要继续循环
            if p * q == n and is_prime(p) and is_prime(q):
                print(p, q)
                end = time.time()
                print(end-start)
                exit(0)
 
# 第二轮：优化一下 is_prime()
def prime_02(n):
    start = time.time()
    for p in range(1, n//2+1):
        for q in range(1, n//2+1):
            # 如果找到因子且两个因子均为质数，则可以直接得出结论，不需要继续循环
            if p * q == n and is_prime(p) and is_prime(q):
            # if is_prime(p) and is_prime(q) and p * q == n:
                print(p, q)
                end = time.time()
                print(end-start)
                exit(0)

三、极端情况