How to iterate through large sets of numbers efficiently?

Question

So i have the following problem: I need to cover the whole interval from $1$ to $10^{12}$ on a computer program. But i can´t do it on a for loop because it would be too slow. So can i iterate over a smaller amount ($\sqrt{n}$ for instance), and still cover the whole interval?

What i've done so far:

Iterate from $1$ to $\sqrt{n}$, then cover $(n-i)$, $\frac{n}{i}$,$\frac{n}{n-i}$.

But i'm still missing some numbers.

Thanks in advance.

Answer 1

If you have to examine every one of those numbers you will have to execute some code $10^{12}$ times. It doesn't matter how cleverly you organize the loop.

Some languages (for example, Python) can optimize looping for you by clever indexing ("vectorizing") that saves a little of the looping overhead - but not the essential calculations.

Edit in response to comment. If you want to look only at primes in that range, consider reading this file:

http://compoasso.free.fr/primelistweb/page/prime/liste_online_en.php

Answer 2

The optimization depends on what you want to do with numbers in the interval. Example: 1. If you want them to write them to a file then there is no optimization you can do. 2. If you want to find out multiples of 1000, then it is possible to optimize the loop to 10^9 iterations.

The approach you tried will only change the order in which numbers are processed but you will still need to process all numbers.