Title description

A sum Numbers (inverse number of primes, first to review how to judge whether a number is prime), remove the lowest, the rest of the number is still the sum Numbers, then remove the number of the rest of the lowest, remaining number or sum Numbers, so repeatedly, until the last one of the remaining digits are sum Numbers, we call such a number of pure sum Numbers, existing n (1 & lt;=n<=1000000) is a natural number x (1 & lt;=x<=100000), please determine whether pure sum Numbers if it is, please output "Yes", otherwise output "No", the last number and output statistics,

Input format

Input line number is unknown, enter 0 means input end,

The output format

According to input output lines, the last line of the output number of pure sum Numbers,

Input and output sample

Enter
9
111
400
402
0
O
Yes
No
Yes
Yes
3
Instructions/tip

The first ten points will timeout? We carefully look at the topic can be found that the data up to 1000000, and numerical maximum 100000, so a large number of duplicate data in the input data (there are a lot of numerical judgement may repeat pure sum Numbers of time is wasted so many times), try to change a train of thought: first determine whether the number all within 1-1000000 for pure sum Numbers judgment results stored in an array, and then on the input data is read the results in an array individually judgment,

do so

CodePudding user response:

Memory read, write, and the time it takes is much bigger than the time required for the CPU calculation, more not to 1000000 just a range,

CodePudding user response:

do look, have the right solution

CodePudding user response:

This question is very simple ah... Pretreatment to heavy, and then sieve method of prime number should be 0 ms

CodePudding user response:

Yes, but this is a composite filter

CodePudding user response:

And pay attention to the definition of pure sum Numbers