????大家应该都会求n以内的所有质数,用的估计都是暴力法,但是当n非常大时,效率会大大降低,如果在笔试时还用暴力,估计会影响测试用例的通过率。这里记录一种最优的求法,时间复杂度可以达到O(n),下面我一步步来从暴力法进行优化:暴力法->暴力优化法->埃筛法->欧拉筛法>。坐稳了老铁~
????发车之前,先来了解几个简单的概念:
素数:只有两个正因数(1和它本身)的自然数即为质数。比1大但不是素数的数称为合数。(1不是质数)
合数:合数是指在大于1的整数中除了能被1和本身整除外,还能被其他数(0除外)整除的数
唯一分解定理:任何一个正整数,可以表示成若干个质数的幂的乘积,且表示方法唯一