关于威兰斯素数公式有效性的疑问及量子计算加速可能性的问询

Hey there! Great question—let’s unpack this from both a mathematical and practical perspective.

First, on whether Willan’s formula is "valid": You’re totally right that pure mathematics doesn’t care about physical limitations like computation time. In a strict theoretical sense, Willan’s formula is a valid equation for generating primes. It logically produces prime numbers without contradiction, so there’s no mathematical reason to dismiss it as "invalid."

The confusion comes from the difference between "mathematically correct" and "useful for generating primes." When people say it’s not a practical prime generator, they’re talking about its computational feasibility. Willan’s formula relies on iterative calculations that blow up in complexity extremely quickly—even to get a relatively small prime, you’d need to perform an enormous number of steps, with intermediate values growing to absurd sizes. For all intents and purposes, classical computers can’t compute it in a reasonable timeframe for any prime larger than the smallest ones. So it’s not that the formula is wrong; it’s just that it’s useless for actually generating primes in practice.

Now, about quantum computers: Quantum computing’s big win with primes is Shor’s algorithm, which crushes classical prime factorization. But Willan’s formula’s computation is a different beast—it’s mostly iterative arithmetic and modular operations, not the number-theoretic factorization that Shor’s algorithm targets. Right now, there’s no well-established quantum algorithm that would drastically speed up the specific steps needed for Willan’s formula.

Could quantum computers help? Maybe, in theory—if we could map the formula’s iterative steps to quantum operations that reduce the computational burden. But even if we did, the formula’s inherent structure means it’s still going to be a cumbersome process. Quantum computers might cut down the time, but they probably wouldn’t turn it into a practical tool for generating primes the way we’d want (like for cryptography or large prime research).

备注：内容来源于stack exchange，提问作者Tsar Asterov XVII