301267: CF237C. Primes on Interval
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:1
Solved:0
Description
Primes on Interval
题意翻译
【题面】 你决定用素数定理来做一个调查. 众所周知, 素数又被称为质数,其含义就是除了数字一和本身之外不能被其他任何的数字除尽. 现在给定一个正整数序列 $a,a+1,\cdots,b$ $(a \le b)$, 请找出一个最小值 $l$, 使其满足对于任意一个长度为 $l$ 的子串, 都包含 $k$ 个质数. 找到并输出符合要求的最小值 $l$, 如果不存在符合要求的长度 $l$, 则输出 $-1$. 【输入格式】 输入一行, 包含三个用空格隔开的整数 $a,b,k$ ($1 \le a,b,k \le 10^{6}; a \le b$) 【输出格式】 输出一行, 为符合要求的最小值 $l$, 若不存在, 输出 $-1$.题目描述
You've decided to carry out a survey in the theory of prime numbers. Let us remind you that a prime number is a positive integer that has exactly two distinct positive integer divisors. Consider positive integers $ a $ , $ a+1 $ , $ ... $ , $ b $ $ (a<=b) $ . You want to find the minimum integer $ l $ $ (1<=l<=b-a+1) $ such that for any integer $ x $ $ (a<=x<=b-l+1) $ among $ l $ integers $ x $ , $ x+1 $ , $ ... $ , $ x+l-1 $ there are at least $ k $ prime numbers. Find and print the required minimum $ l $ . If no value $ l $ meets the described limitations, print -1.输入输出格式
输入格式
A single line contains three space-separated integers $ a,b,k $ ( $ 1<=a,b,k<=10^{6}; a<=b $ ).
输出格式
In a single line print a single integer — the required minimum $ l $ . If there's no solution, print -1.
输入输出样例
输入样例 #1
2 4 2
输出样例 #1
3
输入样例 #2
6 13 1
输出样例 #2
4
输入样例 #3
1 4 3
输出样例 #3
-1