P1619 The Trouble with Solving Quadratic Equations.

JosephZheng was doing prep for his math homework. He often used a Casio to help solve quadratic equations. However, Casio has a problem: when $\Delta=b^2-4ac$ is a large prime or a large composite, its square root is displayed as a decimal rather than the teacher-required radical form. JosephZheng was quite troubled and had to solve such equations by hand whenever this happened. One day he could not stand it anymore, so he turned on his computer and wrote a prime program... and thus the unfortunate OIers had to follow the crazy JosephZheng and write this program together, hehe....

Enough chatter. Given a large number $N$ (possibly greater than $4 \times 10^7$), determine whether it is prime, and then factor it into primes. Of course, junior high school problems will not ask you to test primality for numbers greater than $4 \times 10^7$, so numbers beyond this range can be ignored. To make the program more user-friendly, JosephZheng added some requirements that specify the exact behavior in input and output.

A large number $N$ ($N$ is a non-negative integer), where arbitrary symbols can be inserted between its digits (including a minus sign and a decimal point, which should also be ignored). For example, $1234$ could appear as `1 - 2alsdkjf3！@￥%！@@@##￥……！￥#-4`, etc. You need to extract the number to be checked from this long garbled string. The input testdata may contain multiple cases. Stop when a line containing no digits is read. It is guaranteed that there are at most $100$ test cases, and each string has length at most $1000$.

Before reading the data, first output `Enter the number=` and print a newline. Then output `Prime?`, followed by a space after the question mark, but do not print a newline yet. If the number is prime, output `Yes!`; otherwise, output `No!`. Then print a newline. If it is prime, halt. If it is less than $2$, then after printing `No!`, also halt. If it is composite, factor it into prime factors. If the number is greater than $4 \times 10^7$, output `The number is too large!`, then halt. Otherwise, factor it into prime factors. The exact output format for the factorization will be specified in the sample output. Print a blank line between consecutive test cases. (halt: stop processing this test case).

The author JosephZheng was a bit bored, but this really tests your basics. Read the problem carefully. A straightforward problem.... Translated by ChatGPT 5