Generating all primes is just as easy as testing for primes: def is_prime(n): for m in range(2,int(math.sqrt(n))+1): if n%m == 0: return False return True def primes(): n = 2 while True: if is_prime(n): yield n n += 1 for p in primes(): print p it's just that we don't have useful ways to generate primes. import math
And in 2019, I just entered the phrase "is 4294967297 prime" into a search engine. That level of effort might explain why I only got two out of three of the examples above correct (no better than chance!) before looking at the solutions. But #1 stumped Fermat too! I didn't know that this problem sparked Euler's interest in number theory, according to "How Euler Did It" (4-page PDF). It was one of the many problems left over from the famous Fermat-Descartes correspondence. I figured Euler must have scribbled out a lot of long division problems to crack the Fermat number conjecture. But apparently he found a shortcut. [SPOILER]Fermat and Descartes did not like each other very much. In fact, some people describe their relationship as a “feud,” but it seems that Descartes resented Fermat more than Fermat disliked Descartes. They probably never met.
Euler’s mentor in St. Petersburg, Christian Goldbach, alerted Euler to the conjecture in 1729. Euler responded almost immediately that he could make no progress on the problem, but by 1732, close to a hundred years after Fermat had originally made the conjecture, Euler had a solution: Fermat was wrong. In Euler’s first paper on number theory [E26] Euler announced that 641 divides 4,294,967,297.... What Euler did not tell us in E26 was how he thought to try to divide 4,294,967,297 by 641. He hadn’t simply been dividing by prime numbers until he got to 641. He had a much better way, but he waited about fifteen years, until E134, to reveal that secret.