'''
Created on 2012-3-10
@author: daweibalong
'''
from random import randint
f=[]
def gcd(m,n):
if n>0:
return gcd(n,m%n)
return m
def isPrime(n):
if n<2:
return True
for i in range(2,int(n**0.5)+1):
if n%i==0:
return False
return True
def ifenough(num):
m=1
for i in f:
m*=i
if m==num:
return 0
if m>num:
return 1
return 2
def PollardRho(num,n):
if(isPrime(n)):
f.append(n)
return;
x=[]
i=1
x.append(-1)
x.append(randint(1,n))
y=x[1]
k=2
while True:
i+=1
x.append((abs(x[i-1]*x[i-1]-1))%n)
d=gcd(abs(y-x[i]),n)
if d>1 and d<n:
PollardRho(num,d)
PollardRho(num,n/d)
if i==k:
y=x[i]
k=2*k
if x.index(x[i],0,i+1)!=i or ifenough(num)==0 or ifenough(num)==1:
break
def repeat(n):
while True:
f[:]=[]
PollardRho(n,n)
if ifenough(n)==0:
f.sort(cmp=None, key=None, reverse=False)
for index,j in enumerate(f):
if index!=len(f)-1:
print j,'*',
else:
print j
break
if __name__=='__main__':
print 'please enter the number you want to divide:',
n=int(raw_input())
repeat(n)
分享到:
相关推荐
数据结构中的一种重要随机算法--Las Vegas算法,它总是给出正确的结果,但在少数应用中,可能出现求不出解的情况。也是用了50,500,5000子串验证的
skybox对拉斯维加斯某公路的凝视,可以看到路面的汽车穿梭如织,展示多目标检测和跟踪结果
这是本科算法(DS,DATA STRUCTURE)课程中中最重要的三种算法:KMP, Monte Carlo 和Las Vegas算法。资源里有做好的KMP, Monte Carlo 和Las Vegas算法代码以及2份算法报告。
关于概率随机算法,包含数值随机算法,las Vegas算法,Monte Carlo算法,Sherwood算法
N皇后问题Las Vegas优化算法的实现
随机算法实现N皇后问题,所用随机算法是Las Vegas随机算法
哈工大算法实验四,随机算法求解八皇后问题 Las Vegas算法 1.实现了随机算法与回溯法相结合 2.有界面源代码和实验报告!均为自己所做,正确运行。报告中还有用Excel表分析了算法的性能
稀疏非负卷积的确定性和拉斯维加斯算法_Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution.pdf
las-vegas.zip
这是东南大学计算机系数据结构(data structure)的KMP, Monte Carlo 和Las Vegas算法的程序类实现,里面有代码,报告。
基于Vegas拥塞控制算法提出了一个适合于LEO卫星网络环境的TCP拥塞控制算法(Vegas-AB),该算法是Vegas算法和Vegas-A算法的调和,可以动态地改变Alpha、Beta,Vegas-AB算法与Vegas-A算法的主要分支大体保持一致。...
算法-Python 存储库课程,包括实现(在Python中)和几种计算,数学和统计算法的描述。 尽管它不打算一本正式的书,但我们还是尽量忠实于原始算法,只是在出于教学目的而必须使用变体的情况下,才添加这些变体。 ...
随机快速排序、随机选择、随机采样这三种算法的实现,并且,采用直接读取后台数据,不需要手工输入
利用随机算法判断某个串是否为另一个串的字串 利用随机算法判断某个数是否为素数(较大的素数,20万以上)
R用户组 这是Las Vegas R Users Group的存储库
Vegas_AB:改善Vegas与Reno之间的公平性,徐兵,张旭,尽管TCP Vegas比TCP Reno可以达到更好的吞吐以及更低的重传率,但其在推广过程中仍有不少阻碍。研究表明Vegas在与Reno共享带宽时表现得不�
Vegas随机转场脚本可以轻松解决做视频或者电子相册时遇到的给每个转场添加脚本的困难。打开Vegas--工具--运行脚本
八皇后问题的MonteCarlo算法与回溯法的混合实现,代码精确实现,实验报告或者说论文有详细的阐述!
资源分类:Python库 所属语言:Python 资源全名:nashvegas-0.6.3.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
自己根据拉斯维加斯算法,写的一个用来求解八皇后问题的python程序,其中可以自定义棋盘大小,显示程序的执行时间。