素数题目总结及mr判断素数 _判断素数

素数水题lv_16（大概是只需要打表加遍历，，，也不需要思考，也不会超时，更悲痛的是，换了个题干，结果做法一模一样，或者是微改，微到什么程度呢？大概是改改输出格式、输出内容吧！）
* 数素数呵呵哒，看起来好像很有恐怖什么2的次幂啥的，都是虚晃一招，实际上求前缀和就好了
*哥德巴赫猜想集结……简直了，要不然找对数，要不然找最远的（从2开始遍历），要不然找最近的（从一半开始，偶数-1）。。。
*大概前缀和求区间内素数个数的题目也挺多的吧！
* （CF-999B）反转一到它的因子位置的所有字符，难度在于反转不太好搞，仔细一看就是将因子位置--的字符跟第i++个字符换一换（从有点难降下来的！我容易嘛！）
素数有点难耶lv_8（大概会超时？需要优化，需要一点思考）
*HDUCuts 难点：从输出位于中间的素数，需要判断到n之前有几个质数以确定打印奇数个还是偶数个。解决方案：判断问题，因为数据量小，只有1000，只需要遍历计数就可以。输出：st=(num-c)/2+1; en=st+c-1（这个是试出来的。。。每个人的都不一样，不过(num-c)/2这个要好好记记。这个题PE有点多。。。那个空格的放的位置，跟最后一行的空格有点emmm
* 素数回文难点：容易超时，容易爆内存、数组不好开。解决方案：①先判断素数，在判断回文数②素数打表③内最大的素数为，是很大，是个很好的突破口，这个常用！！！
* E.迷雾森林将n分成好几组素数，一开始想暴力分组，再一想果然不行，人家要的是分组的情况数目。看了题解得知，分组不就是分解成质因子相加吗！再推，得到的就是打表所有素数，然后判断所有的1~n/2即可（一下子看prime[i]和prime[num-i])，不过我还是有点疑问昂，为什么因子不能是3个呢。
* Prime Time本来想当个水题放过去，但是怎么说也是写了个前缀和的啊，而且第一时间我居然没想到前缀和，很难受，放在这里提醒一下我自己。
*-prime H-给了一些公式，求满足条件的数，有个不明白的地方是当他们再找那个数的时候明明都是要素数结果过程中却默认全都是素数，用这些数找满足情况的数字。
*哥德巴赫猜想（升级版）（洛谷-P1579）事实证明，菜鸡永远都是菜鸡，只要换换题型就不会了。这个不同的是三个因子了，遍历第一个因子，再遍历第二个因子，再通过数字判断第三个因子，呵呵哒~
*Bi-shoe and Pi-shoe是一个看起来像是欧拉函数的素数题目，讲的是找到第一个欧拉函数大于等于n的数字，因为素数的欧拉函数一定是它本身减去1，所以这个题目就是这样一个个去找，找到大于x的第一个素数啦~很简单吧~（思路一点都不简单呢！）
素数好难啊！！lv_3（很难相出解题方法，需要结合别的性质、定理、算法！要不然就特别需要优化）
* Sum ofPrime这个涉及到一个尺取法，记录ing，看了解析，这个题目完全是为尺取法量身打造的！附加大佬解析：看me看me~~，因为暴力需要前缀和+循环记录开始，时间复杂度高，就有了这个时间复杂度O(n)的算法。
尺取法个人理解：尺取法通常是对数组保存一对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。这个应该可以取代暴力枚举区间！

文章插图
用i、j分别表示区间的开始结束，如果区间和太小，i+1，sum加上新的数字，如果太大j+1，sum减去刚刚丢掉的小尾巴，直到相同（数据必须要有解）。
很简单吧！好喜欢这个算法哦（因为简单好想嘻嘻）