本人小白一只，今天闲来无事就开了这场重现赛去锻炼一下，哪知第一题便一直TLE，于是我便去找了一些关于此优化的数学知识
先看看我TLE的弱鸡代码（只附上主要部分）
说一下我的瞎搞思路，我想的是每一个数可以拆成一个质数的倍数，然后我就开始筛呗，2肯定是质数所以我就从2开始循环，这个代码最终结果是正确了，但TLE啊，这就是不会数学知识瞎搞的后果
然后我想到之前某位学长聚聚好像给我们讲过一些关于素数的基本知识，于是我便找到了当时的资料来补补数学知识
第一种方法：埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。（发现自己代码打错了一个地方啊啊啊 我太菜了 应该是 ！prime[i] )
第二种方法：（强大到不行）是一种线性筛法，其实很上面的方法很像，它之所以是线性是因为它不再重复去筛选一个和数了，比如36和29，这就减少了循环次数，增强了效率
其实这道题说到底便是一道找最小质因子的题啊，也就是咱们这个线性筛法的变形，只要在原有代码上加几步就好了
（这就是wa了我这个菜鸡五次的题哈哈哈，我太菜了）
京公网安备 11010502036488号