LCC '18 Contest 2 S4 - Superprime

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 3.0s
Memory limit: 256M

Author:
Problem type

Reyno recently realized that his birth year, 1997, has a special property: no digit of 1997 is equal to zero and each suffix of 1997 (1997, 997, 97, 7) is prime. He has decided to call any number with this property a superprime. Now, he wonders how often superprimes occur.

Given an integer N, can you compute the number of superprimes less than N?

Input Specification

The first line of input contains a single integer N (1 \le N \le 10^{18}).

For 30\% of the points, 1 \le N \le 10^6.

For 70\% of the points, 1 \le N \le 10^{12}.

Output Specification

The number of superprimes less than N.

Sample Input 1

10

Sample Output 1

4

Sample Input 2

100

Sample Output 2

15

Comments


  • -4
    Dmoj  commented on Dec. 12, 2019, 2:13 a.m.

    Clues please? I was thinking of using sieve of eratosthenes, but N<=10^18, and just checking if each one is a superprime will obviously TLE