Is it possible to prove that a general purpose integer factorization algorithm must contain a loop? 1) 
Let $A$ be a (general purpose) algorithm that factors $n$. Suppose $A$ contains a loop (which is hard to imagine if not impossible that it does not.) If $A$ contains nested loops then these loops can be combined to one loop. If $A$ contains more loops in sequence, then these loops can also be combined to one loop. 
So suppose that $A$ contains exactly one loop. Since $A$ must finish the factorization after finitely many steps and output $x$ with $1 &lt; x &lt; n$, $x|n$, there must be an if-then statement which tests if $1 &lt; x &lt; n$, $x|n$ or any other mathematically equivalent test. Hence in each step $1,\cdots,t$ we have a number $a_i \in \mathbb{N}$ which is tested. But then letting $g_i = \gcd(a_i,n)$ we have $1 \le g_i \le n$. It could happen that $g_i = g_j$ for $i \neq j$.

Heuristic: We imagine that the numbers $g_i$ are drawn with replacement from the urn $\{1,\cdots,n\}$. 

2) Let $n=pq$ be the prime decomposition of $n$ and let $n=2^e$.
Let us suppose that $p \equiv q \equiv \sqrt{n}$.
Let $p_n$ be the probability to have a number $1 \le x \le n$
with $1 &lt; \gcd(x,n) &lt; n$ and as such to also have a non-trivial factor of $n$.
Then we have
$$p_n = 1-\frac{\phi(n)}{n}=1-\prod_{p|n}{(1-\frac{1}{p})} = 1-(1-\frac{1}{p})(1-\frac{1}{q}) $$
$$ = 1-(1-\frac{1}{\sqrt{n}})^2 = 1-(1-\frac{1}{\sqrt{2^e}})^2 $$
Suppose there exists a factoring-algorithm which runs in polynomial time $f(e)$ which draws with replacement a number $x$ and computes $\gcd(x,n)$.
Let $X$ be the number of numbers $x$ with $1 \lt x \lt n$ and $1 \lt \gcd(x,n) \lt n$ which the algorithm
finds after $f(e)$ steps. Then by definition of the algorithm we must have
$ 1 = P(X \ge 1) $
But on the other hand we have
$$ P(X\ge 1) = 1 - P(X=0) = 1 - (1-p_n)^{f(e)}  $$
$$= 1-(1-\frac{1}{\sqrt{2^e}})^{2 \cdot f(e)} $$
The last equality is by definition of the algorithm valid for every $e$.
But for $e \rightarrow \infty$ we have
$$1 = P(X \ge 1) = 1-(1-\frac{1}{\sqrt{2^e}})^{2 \cdot f(e)} \rightarrow_{e \rightarrow \infty} 0$$
hence for $e \rightarrow \infty$ we have the contradiction $1 = 0$.

My question is, if someone has an idea how to replace the condition $p \equiv q \equiv \sqrt{n}$ with a more rigorous condition.
My second question is, how does one prove, that no (general purpose) factoring algorithm can do without a loop? Maybe using Kolmogorov complexity of the primes to be factored?

Edit:
As @D.W. pointed out the heuristic with $g_i$ is clearly wrong. What I meant to write is that we imagine that the $a_i$ are chosen with replacement from the urn $\{m,m+1,\cdots,M-1,M\}$, where
$ m = \min_i(a_i), M = \max_i(a_i)$. Let $N= M-m+1$ and $N_1 = |\{ k | m \le k \le M, \gcd(k,n)=1 \text{ or } \gcd(k,n)=n\}|$. Then the probability $p_n$ to have a non-trivial factor of $n$ is $p_n = 1 - \frac{N_1}{N}$
If $X$ counts the number of successes of the algorithm , then by definition of the algorithm we must have:
$$1 = P(X \ge 1) = 1-P(X=0) = 1-(1-p_n)^t$$
Now for this argument to be valid, one would need a number theoretic formula for $N_1$.
Also what I meant with loop is not the reading of the number $n$ but a loop for "the search for the solution".
If there is such a loop which produces the numbers $a_1,\cdots,a_t$ then there must be a criterion to stop the loop after $t$ steps.
The loop will terminate earliest when an $x$ ( a solution) such that $1&lt;x&lt;n$ and $1 &lt; \gcd(n,x) &lt; n$ is found. So in this fashion, one might see the statement, "there must exist an if-then statement such that..".
It depends on the precise model of computation you work within.  However, this doesn't seem to be a useful direction for proving lower bounds on the time to factor.

Uniform algorithms

Let's look at uniform algorithms.  Suppose our model of computation is a Turing machine or the transdichotomous model or something similar, where each step can do at most a constant amount of work (or a logarithmic amount of work).  Then any such algorithm must contain a loop or backward branch.

(Why?  Such an algorithm must work on inputs of all possible lengths.  The algorithm has finite length, say length $k$.  If there are no loops or backward branches, then this means that any execution of the algorithm must involve at most $k$ steps, where $k$ is fixed.  This means there exists $n$ large enough so that, when the input is $n$ bits long, the algorithm can't even read the entire input using $k$ steps of computation. Consequently, any such algorithm without loops cannot possibly be correct on all inputs.)

This doesn't seem useful for proving non-trivial lower bounds on the complexity of factoring.

Non-uniform algorithms

Non-uniform algorithms don't require loops.  In particular, if there is a non-uniform algorithm (possibly with loops) that takes $T(n)$ time on $n$-bit inputs, then there is a non-uniform algorithm without loops that takes $O(T(n)^2)$ time on $n$-bit inputs and has size $O(T(n)^2)$.

(Why?  Simply unroll all loops.  Since the algorithm takes $T(n)$ time, each loop will execute at most $T(n)$ times, so you can unroll it and make $T(n)$ copies.)

Other notes

Your question claims "there must be an if-then statement which tests if $1&lt;x&lt;n$, $x|n$ or any other mathematically equivalent test", but this claim is not justified and I don't think it is correct.  There could be algorithms that contain a loop with some other loop condition.  Also, your heuristic is clearly false.  The output of $\gcd(a_i,n)$ isn't anything like a uniformly distributed number from $\{1,\dots,n\}$.  So the direction you're taking seems like it is based on faulty premises and seems like a dead end.