fork download 
  1. def solve_ver1(n):
  2. 	def gcd(a, b):
  3. 		while b: a, b = b, a % b
  4. 		return a
  5. 	result = 1
  6. 	for i in range(2, n + 1):
  7. 		result = result // gcd(result, i) * i
  8. 	return result
  9.  
  10. def solve_ver2(n):
  11. 	sieved = [False] * (n + 1)
  12. 	result = 1
  13. 	for i in range(2, n + 1):
  14. 		if not sieved[i]: # i — очередное простое число
  15. 			for j in range(i, n + 1, i): # выкалывание составных, кратных i
  16. 				sieved[j] = True
  17.  
  18. 			x = i # x будет максимальной степенью i, не превышающей n
  19. 			while True:
  20. 				nx = x * i
  21. 				if nx > n: break
  22. 				x = nx
  23. 			# в новом синтаксисе этот цикл можно записать как while (nx := x * i) <= n: x = nx :^)
  24.  
  25. 			result *= x
  26. 	return result
  27.  
  28. print(solve_ver1(100))
  29. print(solve_ver2(100))
Success #stdin #stdout 0.02s 27712KB
comments (?)
stdin 
Standard input is empty
stdout 
69720375229712477164533808935312303556800
69720375229712477164533808935312303556800
https://ideone.com/8gcxk6
language:
Python 3 (python  3.12)
created:
6 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!