fork download
copy 
  1. from random import randint
  2. import math
  3.  
  4. def fermat(n):
  5. 	x = math.floor(math.sqrt(n))
  6. 	y = 0
  7. 	factors = []
  8. 	if n == x**2:
  9. 		factors.append(x)
  10. 		return factors
  11. 	else:
  12. 		x = x + 1
  13. 	while True:
  14. 		if x == (n + 1) // 2:
  15. 			return factors.append(n)
  16. 		else:
  17. 			y = math.sqrt(x**2 - n)
  18. 			if math.floor(y)**2 == (x**2 - n):
  19. 				factors.append(x+y)
  20. 				factors.append(x-y)
  21. 				return factors
  22. 			else:
  23. 				x = x + 1
  24.  
  25. def binexp(a, n, mod=1):
  26. 	res = 1
  27. 	while n != 0:
  28. 		if(n&1):
  29. 			res = res*a % mod
  30. 		a = a*a % mod
  31. 		n = n >> 1
  32. 	return res
  33.  
  34. def ftest(n, times):
  35. 	result = False
  36. 	for i in range(times):
  37. 		a = randint(0, n)
  38. 		if binexp(a, n, n) == a:
  39. 			result = True
  40. 		else:
  41. 			return(False)
  42. 	return(result)
  43.  
  44. if __name__ == "__main__":
  45. 	n = 34649*71473
  46. 	print(ftest(34649, 11))
  47. 	print(ftest(71473, 11))
  48. 	print(ftest(n, 11))
  49. 	factors = fermat(n);
  50. 	print(factors);
  51.  
Success #stdin #stdout 0.15s 12248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
True
True
False
[71473.0, 34649.0]
https://ideone.com/ozmFAA
language:
Python 3 (python  3.12)
created:
11 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!