It is, of course, possible to prove that there are an infinite number of primes by observing that for any list of primes $\{p_i\}$, you can form the product and add one to generate a number that is either prime or has a prime factorization that only contains primes not on your list.
If we actually attempt to generate primes using this algorithm we get
the following sequence: 2, 3, 7, 43, 1807, 3263443, ...
If we factorize these numbers we receive
the following sequence: 2, 3, 7, 13, 43, 73, 139, 181, 547, 607, 1033, 1171, ..., which are the only primes that we will generated by this algorithm. (Other primes get trapped into loops mod p, for instance 5 gets trapped in the cycle 2, 3, 2, 3, ... mod 5).
If we examine the ratio of the generated primes vs the total primes up to n we seem to have a falling trajectory, and it would make sense if the ratio converges to 0 as n goes to infinity, these primes seem to be quite rare. This makes intuitive sense if we think about this particular algorithm mod p as needing to generate a 0 mod p before generating any other value it's already generated, we can loosely consider the action of the algorithm as a random draw with replacement, and it's easy to see that the probability of drawing a 0 is much less than drawing any two numbers in a row due to the Birthday Paradox. (That being said, the Euclidean algorithm definitely is not a random process mod p, and I'm not even certain it is particularly well-approximated by one.)
(x-axis is natural numbers and y-axis is the ratio)
(x-axis counts the nth prime and y-axis is the ratio)
Can we prove this ratio tends to zero?
Also beginning with other seed values will generate different sequences. All odd primes will immediately generate 2, so 2 will appear in all such sequences. Are there other primes that appear more often than chance would dictate? Less often?