- #1

- 23

- 0

(x+y) + xy = C

C is known & both x,y,c are even numbers.Whether is it possible to find x & y from this equation?

How many posiible x & y in that equation?

Ex:

(x+y) + xy = 6496

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter aravindsubramanian
- Start date

- #1

- 23

- 0

(x+y) + xy = C

C is known & both x,y,c are even numbers.Whether is it possible to find x & y from this equation?

How many posiible x & y in that equation?

Ex:

(x+y) + xy = 6496

- #2

Zurtex

Science Advisor

Homework Helper

- 1,120

- 1

x = 0

y = C

and

x = C

y = 0

I'm not sure there is any way of tackling it other than a case by case basis for C, sorry.

- #3

- 38

- 0

x=72 and y=88

- #4

- 23

- 0

Thank You very much for replying my queries.I need no of solutions available for this equation,

- #5

Zurtex

Science Advisor

Homework Helper

- 1,120

- 1

Think about what LittleWolf has said:aravindsubramanian said:Thank You very much for replying my queries.I need no of solutions available for this equation,

(x+y) + xy = C

Goes to:

(x + 1)(y + 1) = (C + 1)

So, if you let [itex]\alpha[/itex] be the number of prime divisors of C + 1, do you think you could work out the number of solutions?

I'd try with quite a few varied examples. If you need help factoring numbers just use this web page: http://www.alpertron.com.ar/ECM.HTM

- #6

- 38

- 0

- #7

- 6

- 0

(x+y) + xy = C

C is known & both x,y,c are even numbers.Whether is it possible to find x & y from this equation? How many posiible x & y in that equation?

y = -2 is the only special case

x – 2 – 2x =c

-x = c + 2

x = -c – 2

Find all even c such that x is even.

c = 2n for all integer n.

Thus, for all possible c, y = -2 and x = -c – 2 is a solution.

All other possibilities take this form:

If y = 2 then x + 2 + 2x = c

3x = c – 2

x = (c-2)/3

Find all even c such that x is even.

c = 6n +2 for all integer n

If y = 4 then x + 4 + 4x = c

5x = c – 4

x = (c-4)/5

Find all even c such that x is even.

c = 10n +4 for all integer n

If y = 6 then x + 6 + 6x = c

7x = c – 6

x = (c-6)/7

Find all even c such that x is even.

c = 14n +6 for all integer n

The pattern is valid for all even y, including y = -2 :

c = 2(y + 1)n + y for all integer n

Given c, find all possible x and y

c = 2(y + 1)n + y

Each unique y you find determines a unique x, so we only need to find all possible y’s

c = 2ny + 2n + y

c = (2n + 1)y + 2n

c – 2n = (2n + 1)y

(c – 2n)/(2n + 1) = y

Find all integer n such that (c – 2n)/(2n + 1) is an even number.

If (c – 2n)/(2n + 1) is even then ((c – 2n)/(2n + 1))/2 is an integer.

((c – 2n)/(2n + 1))/2 = (c – 2n)/(4n + 2)

Find all integer n such that (c – 2n)/(4n + 2) is an integer.

Since as the absolute value of n becomes large, (c – 2n)/(4n + 2) approaches (-2)/4 , we know we only need to test a finite number of possible n.

We only need to test all n such that AbsoluteValue (c – 2n) >= AbsoluteValue (4n + 2)

You can verify that the desired range of n is:

If c > -1 then

RoundDown ((-c - 2)/2) up to

RoundUp ((c - 2)/6)

If c < -1 then

RoundDown ((c - 2)/6) up to

RoundUp ((-c - 2)/2)

Create the following computer program:

if c > -1 then

for j := RoundDown ((-c - 2)/2) up to

RoundUp ((c - 2)/6) do

if RoundDown ((c – 2j)/(4j + 2)) = ((c – 2j)/(4j + 2)) then

j is a unique solution and

y = (c – 2j)/(2j + 1)

x = (c – y)/(y + 1)

else

for j := RoundDown ((c - 2)/6) up to

RoundUp ((-c - 2)/2) do

if RoundDown ((c – 2j)/(4j + 2)) = ((c – 2j)/(4j + 2)) then

j is a unique solution and

y = (c – 2j)/(2j + 1)

x = (c – y)/(y + 1)

C is known & both x,y,c are even numbers.Whether is it possible to find x & y from this equation? How many posiible x & y in that equation?

y = -2 is the only special case

x – 2 – 2x =c

-x = c + 2

x = -c – 2

Find all even c such that x is even.

c = 2n for all integer n.

Thus, for all possible c, y = -2 and x = -c – 2 is a solution.

All other possibilities take this form:

If y = 2 then x + 2 + 2x = c

3x = c – 2

x = (c-2)/3

Find all even c such that x is even.

c = 6n +2 for all integer n

If y = 4 then x + 4 + 4x = c

5x = c – 4

x = (c-4)/5

Find all even c such that x is even.

c = 10n +4 for all integer n

If y = 6 then x + 6 + 6x = c

7x = c – 6

x = (c-6)/7

Find all even c such that x is even.

c = 14n +6 for all integer n

The pattern is valid for all even y, including y = -2 :

c = 2(y + 1)n + y for all integer n

Given c, find all possible x and y

c = 2(y + 1)n + y

Each unique y you find determines a unique x, so we only need to find all possible y’s

c = 2ny + 2n + y

c = (2n + 1)y + 2n

c – 2n = (2n + 1)y

(c – 2n)/(2n + 1) = y

Find all integer n such that (c – 2n)/(2n + 1) is an even number.

If (c – 2n)/(2n + 1) is even then ((c – 2n)/(2n + 1))/2 is an integer.

((c – 2n)/(2n + 1))/2 = (c – 2n)/(4n + 2)

Find all integer n such that (c – 2n)/(4n + 2) is an integer.

Since as the absolute value of n becomes large, (c – 2n)/(4n + 2) approaches (-2)/4 , we know we only need to test a finite number of possible n.

We only need to test all n such that AbsoluteValue (c – 2n) >= AbsoluteValue (4n + 2)

You can verify that the desired range of n is:

If c > -1 then

RoundDown ((-c - 2)/2) up to

RoundUp ((c - 2)/6)

If c < -1 then

RoundDown ((c - 2)/6) up to

RoundUp ((-c - 2)/2)

Create the following computer program:

if c > -1 then

for j := RoundDown ((-c - 2)/2) up to

RoundUp ((c - 2)/6) do

if RoundDown ((c – 2j)/(4j + 2)) = ((c – 2j)/(4j + 2)) then

j is a unique solution and

y = (c – 2j)/(2j + 1)

x = (c – y)/(y + 1)

else

for j := RoundDown ((c - 2)/6) up to

RoundUp ((-c - 2)/2) do

if RoundDown ((c – 2j)/(4j + 2)) = ((c – 2j)/(4j + 2)) then

j is a unique solution and

y = (c – 2j)/(2j + 1)

x = (c – y)/(y + 1)

Last edited:

- #8

- 6

- 0

I coded the answer I came up with, and it appears to work.

For c = 6496 the solutions are

(-6498,-2), (-90,-74), (0,6496), (72,88)

For c = -6496 the solutions are

(-2166,2), (-1300,4), (-434,14), (-16,432), (-6,1298), (-4,2164), (-2,6494), (0,-6496)

Here is the pascal code:

program xyc;

Var c,x,y,j: longint; m,n,p,q,r,s:real;

begin

c:=6496;

m:=((-c - 2)/2)-1;

n:=((c - 2)/6)+1;

p:=((c - 2)/6)-1;

q:=((-c - 2)/2)+1;

if (c > -1) then

for j := Round(m) to round(n) do

if (Round ((c-2*j)/(4*j + 2)) = ((c-2*j)/(4*j + 2))) then begin

y := round((c-2*j)/(2*j + 1));

x := round((c-y)/(y + 1));

writeln (x,' ',y); end else

else

for j := Round(p) to round(q) do

if (Round ((c-2*j)/(4*j + 2)) = ((c-2*j)/(4*j + 2))) then begin

y := round((c-2*j)/(2*j + 1));

x := round((c-y)/(y + 1));

writeln (x,' ',y); end;

end. {main}

For c = 6496 the solutions are

(-6498,-2), (-90,-74), (0,6496), (72,88)

For c = -6496 the solutions are

(-2166,2), (-1300,4), (-434,14), (-16,432), (-6,1298), (-4,2164), (-2,6494), (0,-6496)

Here is the pascal code:

program xyc;

Var c,x,y,j: longint; m,n,p,q,r,s:real;

begin

c:=6496;

m:=((-c - 2)/2)-1;

n:=((c - 2)/6)+1;

p:=((c - 2)/6)-1;

q:=((-c - 2)/2)+1;

if (c > -1) then

for j := Round(m) to round(n) do

if (Round ((c-2*j)/(4*j + 2)) = ((c-2*j)/(4*j + 2))) then begin

y := round((c-2*j)/(2*j + 1));

x := round((c-y)/(y + 1));

writeln (x,' ',y); end else

else

for j := Round(p) to round(q) do

if (Round ((c-2*j)/(4*j + 2)) = ((c-2*j)/(4*j + 2))) then begin

y := round((c-2*j)/(2*j + 1));

x := round((c-y)/(y + 1));

writeln (x,' ',y); end;

end. {main}

Last edited:

- #9

- 6

- 0

LittleWolf said:

If the prime factorization of C+1=(P1)^(k1)*(P2)^(k2)*...*(Pn)^(kn) then the number of divisors of C+1 equals (k1+1)*(k2+1)*...*(kn+1). The number of paired solutions becomes the smallest integer >=[(k1+)*(k2+1)*...*(kn+1)]/2 . Take for example x+y+xy=(3^4)*(5^2)*(7^3)-1 then C+1= =(3^4)*(5^2)*(7^3) and there should be (4+1)*(2+1)*(3+1)/2=30 pairs of solutions.

In this case, c = 694574

I ran my program and got 30 nonnegative solutions, as predicted.

If the prime factorization of C+1=(P1)^(k1)*(P2)^(k2)*...*(Pn)^(kn) then the number of divisors of C+1 equals (k1+1)*(k2+1)*...*(kn+1). The number of paired solutions becomes the smallest integer >=[(k1+)*(k2+1)*...*(kn+1)]/2 . Take for example x+y+xy=(3^4)*(5^2)*(7^3)-1 then C+1= =(3^4)*(5^2)*(7^3) and there should be (4+1)*(2+1)*(3+1)/2=30 pairs of solutions.

In this case, c = 694574

I ran my program and got 30 nonnegative solutions, as predicted.

Last edited:

- #10

- 23

- 0

Thank You very much for your excellent workz.Now I am analyzing your solutions.I need only positive x & y.

- #11

- 6

- 0

"I need only positive x & y."

Your original request did not mention this, so I solved the more general problem.

For LittleWolf's c=694574 example, one of the 30 solutions is (0,c)

Here are the 30 solutions:

(0,694574)

(2,231524)

(4,138914)

(6,99224)

(8,77174)

(14,46304)

(20,33074)

(24,27782)

(26,25724)

(34,19844)

(44,15434)

(48,14174)

(62,11024)

(74,9260)

(80,8574)

(104,6614)

(134,5144)

(146,4724)

(174,3968)

(188,3674)

(224,3086)

(244,2834)

(314,2204)

(342,2024)

(404,1714)

(440,1574)

(524,1322)

(566,1224)

(674,1028)

(734,944)

For the original problem, c=6496, and we want to factor 6497=73x89. LittleWolf's analysis calls for 2 solutions:

(0,6496)

(72,88)

LittleWolf is solving for x+1 and y+1, not x and y. The number of solutions is derived from (c+1) = (x+1)(y+1). He calculated the number of solutions of the form ((x+1),(y+1)), where (x+1) and (y+1) are both positive numbers. One of the solutions is always (1,(c+1)). We actually want the solutions in the form (x,y), where x and y are both positve. Littlewolf's solution of (1,(c+1)) translates to (x,y) = (0,c), so this solution does not qualify.

Thus, the number of solutions where both x and y are positive is LittleWolf's calculation minus 1. For c=694574, there are 30 - 1 = 29 solutions.

Here is the revised program. It creates an output file. It only outputs the positive solutions. It only works for positive even values of c. It also includes a counter to output the total number of solutions. For c=694574 it prints out exactly 29 solutions.

program xyc;

Var c,x,y,j,k,t,yprev: longint; m,n:real; fo:text;done:boolean;

begin

c:=214748364;

assign(fo,'c:\freepascal\_xyc.txt');

rewrite(fo);

writeln(fo,'C = ',c); writeln(fo);

writeln(fo,'The solutions to x + y + xy = C');

t:=0;

done:=false;

yprev:=-1;

j:= -1;

k:=round(((c - 2)/6)+1);

if ((c >= 2) and ((round(c/2)) = (c/2))) then

repeat

j:=j+1;

if (Round ((c-2*j)/(4*j + 2)) = ((c-2*j)/(4*j + 2))) then begin

y := round((c-2*j)/(2*j + 1));

x := round((c-y)/(y + 1));

if (x=yprev) then done:=true

else if (x>0) and (y>0) then begin

t:=t+1; writeln (fo,'(',x,',',y,')'); yprev:=y; end; end;

until ((j>k) or done);

writeln(fo); writeln(fo,'Total number of solutions = ',t);

close(fo);

end. {xyc}

Here is a sample output:

C = 214748364

The solutions to x + y + xy = C

(4,42949672)

(12,16519104)

(40,5237764)

(60,3520464)

(64,3303820)

(204,1047552)

(304,704092)

(532,402904)

(792,270804)

(1320,162564)

(2500,85864)

(2664,80580)

(3964,54160)

(6604,32512)

(12504,17172)

Total number of solutions = 15

Your original request did not mention this, so I solved the more general problem.

For LittleWolf's c=694574 example, one of the 30 solutions is (0,c)

Here are the 30 solutions:

(0,694574)

(2,231524)

(4,138914)

(6,99224)

(8,77174)

(14,46304)

(20,33074)

(24,27782)

(26,25724)

(34,19844)

(44,15434)

(48,14174)

(62,11024)

(74,9260)

(80,8574)

(104,6614)

(134,5144)

(146,4724)

(174,3968)

(188,3674)

(224,3086)

(244,2834)

(314,2204)

(342,2024)

(404,1714)

(440,1574)

(524,1322)

(566,1224)

(674,1028)

(734,944)

For the original problem, c=6496, and we want to factor 6497=73x89. LittleWolf's analysis calls for 2 solutions:

(0,6496)

(72,88)

LittleWolf is solving for x+1 and y+1, not x and y. The number of solutions is derived from (c+1) = (x+1)(y+1). He calculated the number of solutions of the form ((x+1),(y+1)), where (x+1) and (y+1) are both positive numbers. One of the solutions is always (1,(c+1)). We actually want the solutions in the form (x,y), where x and y are both positve. Littlewolf's solution of (1,(c+1)) translates to (x,y) = (0,c), so this solution does not qualify.

Thus, the number of solutions where both x and y are positive is LittleWolf's calculation minus 1. For c=694574, there are 30 - 1 = 29 solutions.

Here is the revised program. It creates an output file. It only outputs the positive solutions. It only works for positive even values of c. It also includes a counter to output the total number of solutions. For c=694574 it prints out exactly 29 solutions.

program xyc;

Var c,x,y,j,k,t,yprev: longint; m,n:real; fo:text;done:boolean;

begin

c:=214748364;

assign(fo,'c:\freepascal\_xyc.txt');

rewrite(fo);

writeln(fo,'C = ',c); writeln(fo);

writeln(fo,'The solutions to x + y + xy = C');

t:=0;

done:=false;

yprev:=-1;

j:= -1;

k:=round(((c - 2)/6)+1);

if ((c >= 2) and ((round(c/2)) = (c/2))) then

repeat

j:=j+1;

if (Round ((c-2*j)/(4*j + 2)) = ((c-2*j)/(4*j + 2))) then begin

y := round((c-2*j)/(2*j + 1));

x := round((c-y)/(y + 1));

if (x=yprev) then done:=true

else if (x>0) and (y>0) then begin

t:=t+1; writeln (fo,'(',x,',',y,')'); yprev:=y; end; end;

until ((j>k) or done);

writeln(fo); writeln(fo,'Total number of solutions = ',t);

close(fo);

end. {xyc}

Here is a sample output:

C = 214748364

The solutions to x + y + xy = C

(4,42949672)

(12,16519104)

(40,5237764)

(60,3520464)

(64,3303820)

(204,1047552)

(304,704092)

(532,402904)

(792,270804)

(1320,162564)

(2500,85864)

(2664,80580)

(3964,54160)

(6604,32512)

(12504,17172)

Total number of solutions = 15

Last edited:

- #12

- 23

- 0

Hai J1618

your method is quite simple.But take more time than LittleWolf's method.

your method is quite simple.But take more time than LittleWolf's method.

Last edited:

- #13

- 6

- 0

Here is the final version:

program xyc;

Var c,x,y,n,t,yprev: longint; yy,src:real; fo:text; done:boolean;

begin

c:=214748364;

src:=sqrt(c);

assign(fo,'c:\freepascal\_xyc.txt');

rewrite(fo);

writeln(fo,'C = ',c); writeln(fo);

writeln(fo,'The solutions to x + y + xy = C');

t:=0;

done:=false;

yprev:=-1;

n:= -1;

if ((c >= 2) and ((round(c/2)) = (c/2))) then

repeat

n:=n+1;

yy:=((c-2*n)/(2*n + 1));

if (yy>src) then

if (Round (yy/2) = (yy/2)) then begin

y := round(yy);

x := round((c-y)/(y + 1));

if ((x<y) and (x<>0)) then begin

t:=t+1; writeln (fo,'(',x,',',y,')'); yprev:=y; end

else end

else

else done:=true;

until done;

writeln(fo); writeln(fo,'Total number of solutions = ',t);

writeln(fo,'Logic loop ran n = ',n+1,' times');

close(fo);

end. {xyc}

For c = 214748364 , my new program's repeat until loop only ran 7328 times. For c = 694574 , the loop runs 417 times.

Knowing that that y/2 = (c – 2n)/(4n + 2) is a positive integer makes it possible to solve the problem quickly.

If n < 0 then (c – 2n)/(4n + 2) < 0. So we start with n=0.

Also, if (a,b) is a solution, then (b,a) is a solution also. But we consider them to be the same solution.

y = (c - 2n)/(2n + 1). As n increases, y decreases. Once we find a y <= SquareRoot(c) we know we are done. Why? Because x+y+xy=c. Once y <= SquareRoot(c) is found, any further solutions found will be duplicates, since (a,b) = (b,a) for our purposes. My new program starts at n=0, and stops (done:=true) as soon as a y value <= SquareRoot(c) is found.

The new program prints the loop index, n, to verify how many times the loop ran. We can compare this with the expected value. y = (c – 2n)/(2n + 1) = SquareRoot(c). Square both sides and simplify, and you get a quadratic equation:

(4c - 4)n^2 + (8c)n + (c - c^2) = 0

Using the quadratic formula, we find the expected values are the same as the actual values.

Now here is an interesting thing. For a prime factorization algorithm, the simplest and least efficient way to proceed is to test consecutive odd numbers as factors of (c/2), since c is even. In the worst case, you will have to test all odd numbers up to SquareRoot(c/2).

For our 2 examples, how would the worst case performance compare to my method?

You need to test n = (SquareRoot(c/2))/2 numbers.

c = 214748364, n = 5181, my method = 7328

c = 694574, n = 295, my method = 417

The ratio of (worst case prime factorization) to (my method) is 1:(SquareRoot(2)).

In other words, my algorithm runs slightly longer than the worst case performance of an inefficient prime factorization algorithm.

I expected my algorithm to be slower. What surprises me is how close its performance is to the prime factorization method.

The beauty of my method is that the whole program is only about 20 lines long. The inefficient prime factorization algorithm discussed above would probably require at least 50-100 lines of code, and an efficient prime factorization algorithm that generates prime numbers directly would be even longer.

Here are some links on prime number generation:

http://alumnus.caltech.edu/~chamness/prime.html

http://bach.dynet.com/primes/

http://www.freevbcode.com/ShowCode.asp?ID=2114

http://www.olympus.net/personal/7seas/primes.html [Broken]

program xyc;

Var c,x,y,n,t,yprev: longint; yy,src:real; fo:text; done:boolean;

begin

c:=214748364;

src:=sqrt(c);

assign(fo,'c:\freepascal\_xyc.txt');

rewrite(fo);

writeln(fo,'C = ',c); writeln(fo);

writeln(fo,'The solutions to x + y + xy = C');

t:=0;

done:=false;

yprev:=-1;

n:= -1;

if ((c >= 2) and ((round(c/2)) = (c/2))) then

repeat

n:=n+1;

yy:=((c-2*n)/(2*n + 1));

if (yy>src) then

if (Round (yy/2) = (yy/2)) then begin

y := round(yy);

x := round((c-y)/(y + 1));

if ((x<y) and (x<>0)) then begin

t:=t+1; writeln (fo,'(',x,',',y,')'); yprev:=y; end

else end

else

else done:=true;

until done;

writeln(fo); writeln(fo,'Total number of solutions = ',t);

writeln(fo,'Logic loop ran n = ',n+1,' times');

close(fo);

end. {xyc}

For c = 214748364 , my new program's repeat until loop only ran 7328 times. For c = 694574 , the loop runs 417 times.

Knowing that that y/2 = (c – 2n)/(4n + 2) is a positive integer makes it possible to solve the problem quickly.

If n < 0 then (c – 2n)/(4n + 2) < 0. So we start with n=0.

Also, if (a,b) is a solution, then (b,a) is a solution also. But we consider them to be the same solution.

y = (c - 2n)/(2n + 1). As n increases, y decreases. Once we find a y <= SquareRoot(c) we know we are done. Why? Because x+y+xy=c. Once y <= SquareRoot(c) is found, any further solutions found will be duplicates, since (a,b) = (b,a) for our purposes. My new program starts at n=0, and stops (done:=true) as soon as a y value <= SquareRoot(c) is found.

The new program prints the loop index, n, to verify how many times the loop ran. We can compare this with the expected value. y = (c – 2n)/(2n + 1) = SquareRoot(c). Square both sides and simplify, and you get a quadratic equation:

(4c - 4)n^2 + (8c)n + (c - c^2) = 0

Using the quadratic formula, we find the expected values are the same as the actual values.

Now here is an interesting thing. For a prime factorization algorithm, the simplest and least efficient way to proceed is to test consecutive odd numbers as factors of (c/2), since c is even. In the worst case, you will have to test all odd numbers up to SquareRoot(c/2).

For our 2 examples, how would the worst case performance compare to my method?

You need to test n = (SquareRoot(c/2))/2 numbers.

c = 214748364, n = 5181, my method = 7328

c = 694574, n = 295, my method = 417

The ratio of (worst case prime factorization) to (my method) is 1:(SquareRoot(2)).

In other words, my algorithm runs slightly longer than the worst case performance of an inefficient prime factorization algorithm.

I expected my algorithm to be slower. What surprises me is how close its performance is to the prime factorization method.

The beauty of my method is that the whole program is only about 20 lines long. The inefficient prime factorization algorithm discussed above would probably require at least 50-100 lines of code, and an efficient prime factorization algorithm that generates prime numbers directly would be even longer.

Here are some links on prime number generation:

http://alumnus.caltech.edu/~chamness/prime.html

http://bach.dynet.com/primes/

http://www.freevbcode.com/ShowCode.asp?ID=2114

http://www.olympus.net/personal/7seas/primes.html [Broken]

Last edited by a moderator:

- #14

Zurtex

Science Advisor

Homework Helper

- 1,120

- 1

Plus, given you know the number of prime divisors then you can work out the number of solutions.

Try your method with a much bigger number, somewhere in the region of 10^100 to really test your method.

- #15

- 6

- 0

"your naïve algorithm isn’t that good for factoring a number"

My algorithm is the best solution available for this problem that does not involve factoring.

You don't need to be able to read pascal to notice that this algorithm does no factoring. Also, as explained above, it will run (SquareRoot(c))/2 tests for any number, big or small.

By the way, how can you tell an algorithm is naive if you are unable to read it?

My algorithm is the best solution available for this problem that does not involve factoring.

You don't need to be able to read pascal to notice that this algorithm does no factoring. Also, as explained above, it will run (SquareRoot(c))/2 tests for any number, big or small.

By the way, how can you tell an algorithm is naive if you are unable to read it?

Last edited:

- #16

Zurtex

Science Advisor

Homework Helper

- 1,120

- 1

Well running to sqrt(c)/2 isn't in polynomial time so you can't exactly call it efficient. Oh and I'm afraid the few languages I've programmed in look nothing like Pascal, so it's mainly just gibberish to me.J1618 said:You don't need to be able to read pascal to notice that this algorithm does no factoring. Also, as explained above, it will run (SquareRoot(c))/2 tests for any number, big or small.

By the way, how can you tell an algorithm is naive if you are unable to read it?

I was kind of hoping that this thread would get to more interesting number theory than just a simple program that seen barely above brute force. I thought the Totient Function might even come in to place. The point is, just being able to calculate it through writing a program I didn't think was particularly a solution to the persons problems. If you know the number

Share: