python实现埃特金算法图
时间: 2023-09-29 12:06:51 浏览: 69
Eppstein-Algorithm-in-Python:Eppstein 的算法使用图转换技术。 该模型还可以找到从给定源 s 到图中每个顶点的 K 条最短路径,总时间为 O(m + n log n + kn)。 在 Python 中实现
我不是很清楚你想要的是什么样的图,但是以下是一个简单的实现埃特金算法的 Python 代码,它可以生成一个包含素数的列表:
```
def eratosthenes(n):
primes = [True] * (n+1)
primes[0] = primes[1] = False
for i in range(2, int(n**0.5)+1):
if primes[i]:
for j in range(i*i, n+1, i):
primes[j] = False
return [p for p in range(n+1) if primes[p]]
print(eratosthenes(50))
```
这个代码使用了一个布尔数组 `primes` 来表示每个数字是否是素数。一开始,我们把所有数字都标记为素数,然后从 2 开始,将所有它的倍数标记为非素数。接着,我们找到下一个未标记的素数,重复以上步骤,直到我们找到所有小于等于 n 的素数。
如果你想要将生成的素数列表以图的形式呈现出来,你可以使用 Python 的 `matplotlib` 库来绘制一个简单的散点图,例如:
```
import matplotlib.pyplot as plt
primes = eratosthenes(50)
plt.scatter(primes, [1]*len(primes), marker='x')
plt.show()
```
这个代码将生成一个散点图,其中所有素数都被表示为带有 x 标记的点。如果你希望自定义图表的样式,你可以使用 `matplotlib` 提供的各种函数来设置坐标轴、标签、标题等等。
阅读全文