fork download 
  1. import sys
  2. from random import *
  3.  
  4.  
  5. def wyp(s):
  6. 	sys.stdout.write(s)
  7.  
  8. roz=dict()
  9.  
  10. def GCD(a,b):
  11. 	if a==0: 
  12. 		return b
  13. 	return GCD(b%a,a)
  14.  
  15.  
  16. def sqpow(n,k,m):
  17. 	w=1
  18. 	while(k):
  19. 		if (k%2==1):
  20. 			w=(w*n)%m
  21. 		n=(n*n)%m
  22. 		k=k/2
  23. 	return w
  24.  
  25. def TRM(x,ile):
  26. 	if (x==2 or x==3):
  27. 		return 1
  28. 	if (x%2==0 or x%3==0 or x==1):
  29. 		return 0
  30. 	t=0
  31. 	j=0
  32. 	z0=x-1
  33. 	b=0
  34. 	while (z0%2==0):
  35. 		z0/=2
  36. 		t+=1
  37. 	while(ile):
  38. 		b=sqpow(2+randint(0,x-3),z0,x)
  39. 		if (b==1):
  40. 			continue
  41. 		j=0
  42. 		while (j<t and b!=x-1 and b!=1):
  43. 			b=(b*b)%x
  44. 			j+=1
  45. 		if (b!=x-1):
  46. 			return 0
  47. 		ile-=1
  48. 	return 1
  49.  
  50. def find_factor(z):
  51. 	#print "z=%d"%z
  52. 	if ((z%2)==0):
  53. 		return 2
  54. 	c=randint(0,z-1)
  55. 	x=2
  56. 	y=2
  57. 	d=1
  58. 	while(d==1):
  59. 		tp=(y*y+c)%z;
  60. 		y=(tp*tp+c)%z;
  61. 		x=(x*x+c)%z;
  62. 		if (x>y):
  63. 			d=GCD(x-y,z)
  64. 		else:
  65. 			d=GCD(y-x,z)
  66. 	#print "d=%d"%d
  67. 	return d
  68.  
  69. def rhofact(z):
  70. 	#print z
  71. 	global roz
  72.  
  73. 	if (z==1):
  74. 		return
  75. 	if (TRM(z,4)):
  76. 		if (roz.has_key(z)):
  77. 			roz[z]+=1
  78. 		else:
  79. 			roz[z]=1
  80. 		return
  81. 	f=0
  82. 	while(1):
  83. 		f=find_factor(z)
  84.  
  85. 		if (f!=z):
  86. 			rhofact(f)
  87. 			rhofact(z/f)
  88. 			break
  89.  
  90.  
  91.  
  92. while(1):
  93. 	a=int(sys.stdin.readline())
  94. 	if a==0:
  95. 		break
  96. 	roz=dict()
  97. 	#print a
  98. 	rhofact(a)
  99. 	#print roz
  100. 	keylist = roz.keys()
  101. 	keylist.sort()
  102. 	for x in keylist:
  103. 		wyp(str(x))
  104. 		wyp("^")
  105. 		wyp(str(roz[x]))
  106. 		wyp(" ")
  107. 	wyp("\n")
  108.  
  109.  
  110.  
Runtime error #stdin #stdout 4.99s 6100KB
comments (?)
stdin 
3111989
13091989
3917513949581
0
stdout 
Standard output is empty
https://ideone.com/xXzOK
language:
Python 3 (python  3.12)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!