这是一个程序员的自我修养，一个学术者的自我探索，一个大神的养成之道。
什么是质数？
质数，又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数的数称为质数。
一般我们求质数时都会去计算小于某一个数N的质数而不会不加限定，现在我们以求小于N的质数来说一说优化方式。在我们求质数的过程中一般会用到两种方法试除法和筛选法两种。
试除法
①判断小于N的数X是否是质数，就是从2一直尝试到X-1，这种做法效率最差，并不可取。
②如果X是质数，那么它如果不能被小于X/2的数整除即可，这样算法效率提高一些
③除了2以外，所有的质数都只能是奇数，所以我们可以将数X先试除2，然后尝试从3一直到X/2的所有奇数
④其实判断一个数是否是质数，只需判断一个数能不能被除了1之外小于x的数整除即可，
⑤最后，我们可以利用前面求出来的质数来判断，我们只需判断X能不能被小于x的质数整除即可，这样效率会更高。
筛选法
①定义一个容器，将数据放入容器中，然后遍历其中的数据，将是合数的数据删除，最后剩余的就是质数了
②我们可以定义一个布尔类型的数组容器，将其中的值都赋值为true，在筛选的过程中将不是质数的数作为数组的下标将对应元素的值改为false，最后取出值为true的元素的下标即可
③构造定长的byte数组，数组的每个byte存储8个布尔值，这样性能有了些许提高。
网友评论