当前位置:首页 > 语法入门 > 循环结构 > 正文
SSOJ1034素数判定
396+

题目大意:输入一个不超过9位的整数,若是素数,输出“Yes”,否则输出“No”。

输入

输入一个整数

输出

输出Yes或者No

样例输入

5

样例输出

Yes

解题思路

素数(质数),除了1和他本身以外,没有其他因数,1不是质数也不是合数,也就是说质数有且仅有2个因子。判断n是不是素数,可以通过枚举1到n的数字,看有多少个是n的因子,再根据因子个数判断是不是质数。

程序实现

80分:用变量m统计数字n有多个个因子,因子个数不为2,就不是素数;超时原因:n是9位数的话,时间复杂度O(n)远远超过1千万!

80分:用m统计除去1和n本身两个因子后的因数个数,如果m>0表示有其他因数,或者n<2的也不是素数;时间复杂度一样,仍然超时。

90分:如果找到一个不是1也不是本身的因子,那么n就不是素数,后面还有没有因数也没关系了,提前退出循环。时间复杂度仍然是O(n):如果遇到一个很大的合数,我们可以较快找到他的因子,多得一点点分;如果遇到的是一个很大的质数,还是要枚举2到n-1个数字,超时!

满分:我们发现,因数是成对出现的,如果i是n的因数,那么n/i也是n的因数。这两个因数,一个不超过√n,一个不小于√n。因此,我们只需要枚举2到√n的数就行。及时n是9位数,我们枚举的数字也不超过10000个,不会超时。

 

更多

About

坚决不Copy代码!

本文标签:,,,,,,,,,

SSOJ1034素数判定:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter