求100~200之间的素数
素数又称质数。素数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数;即一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做素数。
解题思路:采用的算法是,让一个数n被i 除(i的值从2变到n-1),如果n能被2~n-1之间任何一个数整除,则n不是素数,即可提前结束循环。
完整代码:
程序改进1:其实n不必被2~(n-1)范围内的每个整数除,只须要被2~ √n 之间的整数除即可。例如判断17是否为素数,只需要将17被2,3和4除即可。这样可以减少循环次数,提高效率。
程序改进2:所有的偶数都不是素数,所以在循环过程中可以只对奇数进行判定,由此可以进行一步提高效率。
运行结果: