LCC '18 Contest 2 S4 - Superprime - MCPT: Mackenzie Competitive Programming Team

LCC '18 Contest 2 S4 - Superprime

View as PDF

Submit solution

All submissions

Best submissions

Points: 12 (partial)

Time limit: 3.0s

Memory limit: 256M

Author:

rtilikay

Problem type

Reyno recently realized that his birth year, $1997$ ~1997~, has a special property: no digit of $1997$ ~1997~ is equal to zero and each suffix of $1997$ ~1997~ $(1997, 997, 97, 7)$ ~(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$ ~N~, can you compute the number of superprimes less than $N$ ~N~?

Input Specification

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

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

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

Output Specification

The number of superprimes less than $N$ ~N~.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Comments

-3

Dmoj commented on Dec. 11, 2019, 9:13 p.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