savinov's blog

By savinov, 10 years ago, translation, In English

Hi, everybody! Recently, I tried to solve a problem. In this problem I had to determine, is number N sum of two squares? i.e. N = a2 + b2?, where a and b are integer. N < 1015. Firstly, I tried to brute-force a and check N - a2 for a square, but got TL. Also I tried to factorize the number and check degree of prime divisors p = 4k + 3 and used Fermat-Euler theorem to check the fact. But also I got TL. I suppose this problem to solve with number of operations . And I'm interested in technical realization of it. Can anybody show how to write accurate brute-force or factorization for example on C/C++? And what advices can you give to write same programs, making as less operations as possible? It's the problem from acm.timus.ru link here Thanks in advance!

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How can you use an algorithm that checks N = a²+b² in the problem you linked? It asks for the minimum number of squares that sum to N, am I right?

»
10 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

according to me we can run a loop in which 'i' goes from 1 to sqrt(N/2) and if N-i*i is a perfect square we are done....

for(int i=1; i*i<=N/2; i++) { if((N-i*i) is a perfect square) done; }

its complexity is O(sqrt(N)).....

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How do you check number for square? I did the same and used sqrt() and got TL.

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

An arbitrary positive number n is expressible as the sum of two squares iff, given its prime factorization

n=p1^(a1)p2^(a2)p3^(a3)...pk^(ak),

none of pi^(ai) +1 is divisible by 4 (Conway and Guy 1996, p. 147). http://mathworld.wolfram.com/SquareNumber.html