1485: 连续素数

文件提交:无需freopen 内存限制:128 MB 时间限制:1.000 S
评测方式:普通裁判 命题人:
提交:1 解决:1

题目描述

曾经有数学家研究过这样一个问题:b为一个常数,当x依次取值为1,2,3,……时,形如x*x+x+b的数是否可能都是素数。如b=41时,形如x*x+x+41的前39个数都是素数,其中第39个数是39*39+39+41=1601,是素数,但当x=40时即第40个数40*40+40+41=1681=41*41,不是素数。现在要你对输入的正整数b,求形如x*x+x+b的数中开头连续的素数有几个?如b=1时,开头5个数是3,7,13,21,31,开头连续的素数有3个,因为第4个数4*4+4+1=21不是素数。

输入

输入一个自然数b(b≤1000)

输出

输出当x依次取值为1,2,3,……时,形如x*x+x+b的数中开头连续的素数有几个?

样例输入

41

样例输出

39

提示

素数又称质数。指在一个大于1的自然数中,除了1和此整数自身外,不能被其他自然数整除的数。如5是素数,因为5只能被1和自身整除;6不是素数,因为6能被2或3整除。本题无论用哪种素数判断方法都不会超时。

来源/分类