| Submit | All submissions | Best solutions | Back to list |
PROG0563 - A Martian census |
There has been a gathering of more than one Martian somewhere in a cave on Mars. These Martians do not really have hands, but they do have some finger-like extensions that are directly attached to their bodies. All Martians have the same number of fingers, and that number is at least two. Altogether there are between 200 and 300 Martian fingers in the cave (including the lower and upper limits). If you knew the exact number fingers in the cave, you could deduce the exact number of Martians. How many Martians are there, and how many fingers does each one have?
The key to the solution of this problem is that the number of fingers can tell us uniquely the number of Martians. That's a tall order. It eliminates, say, 246 fingers because that's too ambiguous: there might be 82 Martians with 3 fingers each or 3 Martians with 82 fingers each, and so on.
The only possibility that avoids this uncertainty is that the quantity of Martians and the quantity of fingers per Martian are expressed by the same number, and that this number is not composite. That means we’re looking for the square of a prime number, and the only such number in the range 200–300 is 289 (or $17^2$). So there are 17 Martians, each of which has 17 fingers.
Input
The input contains two integers $m, n \in \mathbb{N}$ such that $m \leq n$. It is guaranteed that there's only a single prime number $p$ such that $m \leq p^2 \leq n$.
Output
Example
Input:
200 300
Output:
There are 17 Martians having 17 fingers each.
In een grot op Mars zijn er minstens twee marsmannetjes samengekomen. Deze marsmannetjes hebben niet echt handen, maar ze hebben wel een soort van vingers die rechtstreeks met de rest van hun lijf verbonden zijn. Bovendien hebben alle marsmannetjes evenveel vingers, en het zijn er minstens twee. Alles samen bevinden er zich in totaal tussen de 200 en 300 vingers in de grot (grenzen inbegrepen). Als je het totaal aantal vingers kent, dan kan je daaruit op een ondubbelzinnige manier het exacte aantal Marsmannetjes afleiden. Hoeveel marsmannetjes bevinden er zich in de grot, en hoeveel vingers heeft elk van die marsmannetjes?
De sleutel voor het oplossen van dit probleem ligt in het feit dat het totaal aantal vingers ons op een unieke manier verklapt hoeveel marsmannetjes er zijn. Deze vaststelling elimineert bijvoorbeeld de mogelijkheid dat er in totaal 246 vingers zouden zijn, want dat zou te dubbelzinnig zijn. Dat zou immers evengoed kunnen betekenen dat er 82 marsmannetjes zijn die elk 3 vingers hebben, maar ook dat er 3 marsmannetjes kunnen zijn met elk 82 vingers.
De enige mogelijkheid die de onzekerheid volledig wegneemt is dat het aantal marsmannetjes exact gelijk is aan het aantal vingers per marsmannetje, en dat we dit aantal niet verder kunnen ontbinden. We zijn dus op zoek naar het kwadraat van een priemgetal, en het enige getal dat daarvoor in aanmerking komt in het interval 200–300 is 289 (of $17^2$). Er zijn dus 17 marsmannetjes die elk 17 vingers hebben.
Invoer
De invoer bestaat twee getallen $m, n \in \mathbb{N}$ waarvoor geldt dat $m \leq n$. We garanderen hierbij dat er slechts één priemgetal $p$ is waarvoor geldt dat $m \leq p^2 \leq n$.
Uitvoer
Voorbeeld
Invoer:
200 300
Uitvoer:
Er zijn 17 marsmannetjes met elk 17 vingers.
| Added by: | Peter Dawyndt |
| Date: | 2015-09-29 |
| Time limit: | 10s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | PY_NBC |
RSS