Firstly, the number of prime numbers < n grows by roughly n/log(n)
So moving from
2^16 = 65536
to
2^32 = 4294967296
Increases the size of the total potential search space from 5909 to 193635251, which is ~ 5909 x 32769
secondly, the reason it grows by only n^2, is you only need to search along the curve n = a x b - which is the "sieve" part.
if 2^512 calculations costs you $8
then (2^512)^2 calculations costs you $64
Thirdly, your stupidly high costs are because you seem to think you need to check if 4817 x 5693 is a prime fractorisation of 26768069 when in fact you already know the prime factorisation by that point.
> if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64
Can you answer
a) If 1 apple costs you 8$ then (1)^2 apple costs you: ???
b) If 10 apples cost you 8$ then (10)^2 apples costs you: ???
edit: between the price and the amount, usually there is a ~linear relationship. So if you can buy 2^512 something for 8$, then chances are that for 8 times the price you'll only get ~8 times more amount, and not 2^512 times more
The tldr is bigO gives you how the cost of apples changes with the number of apples in the worst case.
its a rough simplification, the precise formula is close but not exactly that. the simplification is also actually (2n)^2 but in my defense I was going from memory of work from more than 2 decades ago (testing generated prime factors were good prime factors, overwhelmingly they were not).
using your apples example
if the bigO of eating apples is O(n^2), and it takes you 8 minutes to eat 2 apples, it will take you no more than 64 minutes to eat 4 apples.
The $8 will vary, and the actual cost function completely depends on the implimentation, its definitely possible to do worse, very likely possible to do better - there was rumors a few years ago that some Riemann surface based math can do it in O(1), but I know nothing about Riemann surfaces so can't judge their veracity.
Cost(n) = search_space(n) * $8 / search_space(16)
And search_space(x) = 2^x so
Cost(n) = 2^n * $2^3 / 2^16 = $2^(n - 13)
Cost(32) = $2^(32 - 13) = $524288 Cost(64) = $2^(64 - 13) = $2251799813685248
So it quickly becomes astronomically expensive.
If you double the number of bits n you get
Cost(2n) = $2^(2n - 13)
You were assuming that Cost(32) = Cost(16)^2, in other words Cost(2n) = Cost(n)^2. But this equality doesn't hold:
Cost(n)^2 = $2^(n - 13)^2 = $2^(2n - 26)
This is significantly smaller than Cost(2n) = $2^(2n - 13) as stated above.
An equation with different units on each side like "512 bit = $8" doesn't work mathematically and will lead to contradictory conclusions.