WONOWON - Wonowon
There is a little village in northern Canada called Wonowon, its name coming from the fact that it is located at Mile 101 of the Alaska Highway. While passing through this village, a wandering mathematician had an idea for a new type of number, which he called a wonowon number. He defined a wonowon number as a number whose decimal digits start and end with 1, and alternate between 0 and 1. Thus, the first four wonowon numbers are 101, 10101, 1010101, 101010101.
Neither 2 nor 5 can divide any wonowon number, but it is conjectured that every other prime number divides some wonowon number. For example, 3 divides 10101 (i.e. 3×3367), 7 divides 10101 (i.e. 7×1443), 11 divides 101010101010101010101 (i.e. 11 × 9182736455463728191).
Assume throughout that this conjecture is true, and let W(p) denote the number of digits in the smallest wonowon number divisible by p. Thus, for example, W(3) = 5, W(7) = 5, W(11) = 21, W(13) = 5, W(17) = 15, W(19) = 17.
It has been found experimentally that for many primes p, W(p) = p − 2 (as in the case for p = 7, 17, 19). Thus, your task is to write a program which reads an integer n and outputs the number of primes for which W(p) = p − 2. Note that p cannot be 2 nor 5, and p is a prime number less-than or equal to n.
Input
The input consists of a single integer 3 ≤ n ≤ 10000.
Output
The output should consist of a single integer representing the number of primes p for which W(p) = p − 2.
Example One
Input: 20 Output: 3
Example Two
Input: 100 Output: 14
hide comments
Piyush Kumar:
2016-06-21 08:59:54
I agree with Tjandra, the source code limit makes this question a bit easier than it actually is:) |
|
(Tjandra Satria Gunawan)(曾毅昆):
2016-04-24 06:33:59
Easy one.. Could be more fun if source limit is < 300B.. |
|
darragh:
2016-03-31 11:38:09
@farhan764
|
|
farhan764:
2016-03-30 23:26:18
PS ....13 is also dividing 10101010101(11 digits)...so that 13 should be in counting....
|
|
Vipul Srivastava:
2016-03-28 11:02:29
It is allowed but you should solve the problem without doing that. Last edit: 2016-03-28 20:37:31 |
|
Ram:
2016-03-28 10:30:32
Can i pre compute the result and use it in my program ? That's not allowed right ? |
Added by: | Darragh Griffin |
Date: | 2016-03-27 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: GOSU |
Resource: | Irish Collegiate Programming Contest 2015 http://acm.ucc.ie/irlcpc |