fork download
copy 
  1. def is_sum_of_two_squares(m):
  2.     """m = 2**a0 * p1**a1 * ... * pi**ai * q1**(2*b1) * ... * qk**(2*bj)
  3.  
  4.  
  5.     p: 4*n+1  Pythagorean primes
  6.     q: 4*n+3
  7.  
  8. https://r...content-available-to-author-only...a.org/wiki/%D0%93%D0%B0%D1%83%D1%81%D1%81%D0%BE%D0%B2%D1%8B_%D1%86%D0%B5%D0%BB%D1%8B%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0#.D0.9F.D0.BE.D0.B4.D1.81.D1.87.D1.91.D1.82_.D1.87.D0.B8.D1.81.D0.BB.D0.B0_.D0.BF.D1.80.D0.B5.D0.B4.D1.81.D1.82.D0.B0.D0.B2.D0.BB.D0.B5.D0.BD.D0.B8.D0.B9_.D0.B2_.D0.B2.D0.B8.D0.B4.D0.B5_.D1.81.D1.83.D0.BC.D0.BC.D1.8B_.D0.B4.D0.B2.D1.83.D1.85_.D0.BA.D0.B2.D0.B0.D0.B4.D1.80.D0.B0.D1.82.D0.BE.D0.B2
  9.     """
  10.     assert m >= 0
  11.     if m < 3:
  12.         # 0*0 + 0*0 == 0
  13.         # 1*1 + 0*0 == 1
  14.         # 1*1 + 1*1 == 2
  15.         return True
  16.     p = 2
  17.     while m > 1:
  18.         multiplicity = 0
  19.         while m % p == 0:  # found prime factor
  20.             multiplicity += 1
  21.             m //= p
  22.         if multiplicity & 1:  # odd power
  23.             if p % 4 == 3:    # 4*k+3 form
  24.                 return False
  25.             else:
  26.                 assert p % 4 == 1 or p == 2
  27.         p += 1
  28.     return True
  29.  
  30.  
  31. def max_sum_of_two_squares_nearest(m):
  32.     """Find maxsum=x*x+y*y such that |maxsum-m| is minimal."""
  33.     for i in range(m + 1):
  34.         if is_sum_of_two_squares(m + i):
  35.             return m + i
  36.         elif is_sum_of_two_squares(m - i):
  37.             return m - i
  38.     assert 0
  39.  
  40. for m in range(21):
  41.     print(m, "->", max_sum_of_two_squares_nearest(m))
  42.  
  43. print(max_sum_of_two_squares_nearest(int(input())))
Success #stdin #stdout 0.01s 27720KB
comments (?)
stdin
copy 
1000000000
stdout
copy 
0 -> 0
1 -> 1
2 -> 2
3 -> 4
4 -> 4
5 -> 5
6 -> 5
7 -> 8
8 -> 8
9 -> 9
10 -> 10
11 -> 10
12 -> 13
13 -> 13
14 -> 13
15 -> 16
16 -> 16
17 -> 17
18 -> 18
19 -> 20
20 -> 20
1000000000
https://ideone.com/asiOS1
language:
Python 3 (python  3.9.5)
created:
6 years ago
visibility:
secret

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!