python写一个判断质数算法
时间: 2024-01-28 13:05:03 浏览: 27
当然!以下是一个用Python编写的判断质数的简单算法:
```python
def is_prime(num):
if num <= 1:
return False
for i in range(2, int(num ** 0.5) + 1):
if num % i == 0:
return False
return True
num = int(input("请输入一个整数:"))
if is_prime(num):
print(f"{num} 是质数")
else:
print(f"{num} 不是质数")
```
这个算法中的 `is_prime` 函数用于判断一个数是否为质数。它从2开始遍历到该数的平方根,如果在这个范围内存在可以整除该数的因子,则该数不是质数。否则,它就是质数。
在代码中,我们首先通过 `input` 函数获取用户输入的整数,并将其传递给 `is_prime` 函数进行判断。然后根据判断结果输出相应的信息。
希望这可以帮助到你!如果还有其他问题,请随时提问。
相关问题
用python 写一个felury算法
### 回答1:
答:Python 的 Felury 算法非常简单,只需要在给定的元组序列中搜索最小值即可。首先,初始化一个字典,其中键为元组,值为无穷大。然后,从给定的元组序列中搜索最小值,并将其存入字典中。最后,返回字典中最小值对应的元组。
### 回答2:
Felury算法(Fleury's Algorithm)是一种用于找出欧拉回路(Eulerian circuit)的算法。欧拉回路是指一条可以遍历图中每条边一次且只一次的闭合路径。
实现Felury算法的Python代码如下:
```python
def fleury_algorithm(graph, start):
# 深拷贝图,避免修改原图
g = graph.copy()
circuit = [start] # 存储欧拉回路的路径
while len(g) > 0:
current = circuit[-1] # 当前访问的节点
neighbors = g[current] # 当前节点的邻居
if len(neighbors) == 0:
# 当前节点没有邻居,将其从路径中移除
circuit.pop()
else:
# 遍历当前节点的所有邻居
for neighbor in neighbors:
# 判断移除当前邻居后是否为连通图
if not is_bridge(g, current, neighbor):
break
# 移除当前边
g[current].remove(neighbor)
g[neighbor].remove(current)
# 将当前邻居加入路径
circuit.append(neighbor)
return circuit
def is_bridge(graph, u, v):
# 判断移除边(u, v)后,图是否为连通图
visited = set()
stack = [u]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
stack.extend(graph[node])
return v not in visited
# 示例使用
graph = {
'A': ['B', 'C', 'D'],
'B': ['A', 'C'],
'C': ['A', 'B', 'D'],
'D': ['A', 'C']
}
start_node = 'A'
euler_circuit = fleury_algorithm(graph, start_node)
print(euler_circuit)
```
以上代码实现了Felury算法。它使用了邻接表表示图,通过深度优先搜索来判断移除某条边后图的连通性。若连通,则移除该边,并将相邻节点添加到路径中,直到所有边都被访问过。最终返回的路径即为欧拉回路。
### 回答3:
Felury算法是一种用于寻找整数的质因数的算法,它是一种较为简单但高效的算法。下面是使用Python语言实现Felury算法的示例代码:
```python
def felury(n):
factors = []
i = 2
while i * i <= n:
if n % i:
i += 1
else:
n //= i
factors.append(i)
if n > 1:
factors.append(n)
return factors
# 测试代码
num = int(input("请输入一个正整数:"))
factors = felury(num)
print(f"{num}的质因数为:{factors}")
```
代码中的`felury`函数接受一个正整数作为参数,然后使用循环从最小的质数2开始,逐步地找出它的质因数,并将这些质因数添加到一个列表中。在每一次循环中,如果给定的整数能够整除当前的质数,就将该质数作为一个质因数,并将整数除以该质数。直到整数变为1或者大于根号n时停止循环。最后,如果整数大于1,说明它本身就是一个质因数。运行结果会打印出给定整数的质因数列表。
用python 写一个rsa算法代码
以下是 Python 实现的 RSA 加密算法代码示例:
```python
import random
import math
# 生成指定长度的质数
def generate_prime_number(length):
while True:
p = random.randint(2**(length-1), 2**length-1)
if is_prime(p):
return p
# 判断一个数是否为质数
def is_prime(n):
if n == 2 or n == 3:
return True
if n < 2 or n % 2 == 0:
return False
for i in range(3, int(math.sqrt(n))+1, 2):
if n % i == 0:
return False
return True
# 求解最大公约数
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
# 扩展欧几里得算法求解模反元素
def extended_gcd(a, b):
if b == 0:
return a, 1, 0
else:
d, x, y = extended_gcd(b, a % b)
return d, y, x - (a // b) * y
# 生成 RSA 密钥对
def generate_rsa_key(length):
p = generate_prime_number(length // 2)
q = generate_prime_number(length // 2)
n = p * q
phi = (p - 1) * (q - 1)
e = 65537
d = extended_gcd(e, phi)[1]
d = d % phi
return ((e, n), (d, n))
# RSA 加密
def rsa_encrypt(m, public_key):
e, n = public_key
c = pow(m, e, n)
return c
# RSA 解密
def rsa_decrypt(c, private_key):
d, n = private_key
m = pow(c, d, n)
return m
```
使用示例:
```python
# 生成 RSA 密钥对
public_key, private_key = generate_rsa_key(2048)
# 加密消息
message = 123456789
ciphertext = rsa_encrypt(message, public_key)
# 解密消息
plaintext = rsa_decrypt(ciphertext, private_key)
print("明文:", message)
print("密文:", ciphertext)
print("解密结果:", plaintext)
```
注意:这只是一个简单的示例,实际应用中还需要考虑一些安全性问题,例如使用更长的密钥长度、使用 padding 等。