Problem Background

JosephZheng is preparing his math homework. He often uses Casio to help solve quadratic equations. However, Casio has an issue: when $\Delta = b^2 - 4ac$ is a large prime or composite number, the square root result is displayed as a decimal, not in the quadratic radical form required by his teacher. JosephZheng is very troubled and has to manually solve the equation whenever this happens. One day, he couldn't take it anymore, so he turned on his computer and wrote a prime program... Thus, the unfortunate OIers have to follow the疯狂的 JosephZheng and write this program, haha...

Problem Description

Enough of the chatter, you are given a large number $N$ (which may not be within the int64 range) for primality testing and prime factorization. Of course, middle school math problems won't have numbers larger than int64 for primality testing, so numbers beyond this range can be ignored. To make the program more considerate, JosephZheng has added some specific requirements, which will be detailed in the input and output.

Input and Output Format

Input Format

A large number $N$ ($N$ is a non-negative integer), where the digits of this number can be interspersed with various symbols, such as 1 - 2alsdkjf3！@￥%！@@@##￥……！￥#-4. You need to find this number to be tested from the long string of gibberish. The input may contain multiple sets of data; if a line without any digits is read, it signifies the end. The string length may exceed 255.

Output Format

Before reading the data, output Enter the number= followed by a newline.

Then output Prime? with a space after the question mark, but do not newline.

If it is a prime number, output Yes!; otherwise, output No!. Then newline.

If it is a prime number or a number less than 2, halt after outputting No!. If it is a composite number, perform prime factorization. If the number is greater than forty million, output The number is too large! and then halt. Otherwise, perform prime factorization. The output format will be detailed in the sample outputs. Leave a blank line between each set of data.

Sample Input and Output

Sample Input #1

4
eed

Sample Output #1

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

Enter the number=

Sample Input #2

2
end

Sample Output #2

Enter the number=
Prime? Yes!

Enter the number=

Sample Input #3

-1
adfs

Sample Output #3

Enter the number=
Prime? No!

Enter the number=

Sample Input #4

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

Sample Output #4

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

Enter the number=

Sample Input #5

1.5
1
1234324123512343123
@~@~@~@

Sample Output #5

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=

Sample Input #6

12
halt@@

Sample Output #6

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

Enter the number=

Notes

JosephZheng, who created this problem, might be a bit bored, but it's quite a test of basic skills! Read the problem carefully!

Just an easy problem...

见题面 Input 部分

见题面 Output 部分