Description

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.

Input Format

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$.

Output Format

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).

4
eed

Enter the number=
Prime? No!
4=2^2

Enter the number=

2
end

Enter the number=
Prime? Yes!

Enter the number=

-1
adfs

Enter the number=
Prime? No!

Enter the number=

1234###24#@13#@￥！1
hehe

Enter the number=
Prime? No!
The number is too large!

Enter the number=

1.5
1
1234324123512343123
@~@~@~@

Enter the number=
Prime? No!
15=3^1*5^1

Enter the number=
Prime? No!

Enter the number=
Prime? No!
The number is too large!

Enter the number=

12
halt@@

Enter the number=
Prime? No!
12=2^2*3^1

Enter the number=

Hint

The author JosephZheng was a bit bored, but this really tests your basics. Read the problem carefully.

A straightforward problem....

Translated by ChatGPT 5