求素数的方法_判断素数为什么是2到根号n

线性筛明天证，还有一些位运算符的小妙用

1.单素数性质(x为整数,6x+4和6x-2本质一样就不写了，余下也是）

可以看到除了2、3以外以及6x前后有可能是素数，剩下都不可能为素数，故判断一个数是否为素数可以先判断是否在6x前后，从而剪枝达到优化。

简单解释下普遍大家都知道的（给新手），就是为啥只到根号n。最开始其实终止条件是到n/2的，很简单嘛，因为n/2之后不可能存在n的因子，因为最小的因子2乘上一个任何一个大于n/2的数肯定比n大，所以之后不存在因子。那为啥能筛到根号n呢，是因为根号n的平方是n本身，根号n后面如果存在n的因子a，那么一定能在n之前找到n/a这个因子，只要有因子就不是素数了，所以没必要反复筛，前面筛完就已经知道不是素数了

#include<bits/stdc++.h> using namespace std; int main() { 
    int n; cin>>n; if(n==2||n==3) { 
    cout<<"是素数"; } else if(n%6!=1&&n%6!=5) { 
    cout<<"不是素数"; } else { 
    for(int i=2;i*i<=n;i++) { 
    if(!(n%i)) { 
    cout<<"不是素数" ; return 0; } } cout<<"是素数"; } } 

简单证明下埃筛

埃筛的核心思路就是标记，即我把所有素数的倍数都标记上，那么之前一直没被标记的就是素数（因为一直标记的是素数倍数，没被标就说明不是素数倍数嘛）。但是要注意，从2开始标（这个很好理解）。好，那么开始解释这一步小优化。就是为啥从素数的平方开始标记

读者：你之前不是说筛素数倍数吗？他平方下的倍数就不用筛了？

其实这个很好解释，因为他平方下的倍数，一定是一个小于他的数乘以该素数，比他平方小的该素数倍数就已经被 比他小的素数筛过了，就没必要再标记一次。

举个栗子，7是素数，为什么14、21、28不用被筛呢，因为他们分别被2、3、2筛过了

推广到普遍形式，a是素数，b（小于a的一个数）*a就一定被筛过了，为什么呢？

假如b是质数，那么好，根据埃筛的条件，a肯定大于b，所以也满足是在bb之后素数倍数的条件，所以ba就已经被b筛过一次了

如果b不是素数，那么肯定可以写成一个最小质因子c任意数d的形式，那就更简单了，b都比c大更别提a了，也满足在cc后c倍数的条件，所以ba也被c筛过一次

从而得证，素数平方前的素数倍数都被筛过一次了，所以可以进行一步小优化，即从素数平方开始筛素数倍数

#include<bits/stdc++.h> using namespace std; int main() { 
    int ans[32766]; vector<int> primes; memset(ans,0,sizeof(ans));primes.clear(); int check; cin>>check; for(int i=2;i<=check;i++) { 
    if(!ans[i])//没被标记就是素数 { 
    primes.push_back(i); } for(int j=i*i;j<=check;j+=i)//从他的平方开始筛，平方内他的倍数被小于他的质数筛过了 { 
    ans[j]=1; } } for(int i=0;i<primes.size();i++) { 
    cout<<primes[i]<<endl; } } 

最后一个很有趣的乘法，俄罗斯农民乘法

他的规则是这样的（你甚至不需要会乘法）

将相乘的两数写在一起

将第一个数×2（不会乘法的可以用加法代替） 第二个数÷2（忽略余数）

直到第二个数为1为止

如果第二个数是偶数，那么就把他所在行划掉

剩下没被划掉的第一列的和就是答案

举个栗子，14*27=378我们来执行下这个操作

14 * 27
28 * 13
56 * 6
112 * 3
224 * 1

我们会惊讶的发现，没有被划掉的第一列相加14+28+112+224=378答案竟然一模一样

剩下所有乘法结果都是一样的，读者可自行尝试

现在来简单证一下，其实就是将第二个数化为了二进制罢了

还是拿刚刚那个举例，27对应的二进制应该是11011那么对应在十进制乘法里应该是1 * 14*2^4

+1 * 14*2^3

+0 * 14*2^2

+1 * 14*2^1

+1* 14*2^0

本质上来说就是将第二个数按照二进制的方法拆分，再分别以2次幂乘回去

那么我们可以看到刚刚的操作其实本质上是：

将第一个数×2 第二个数÷2（忽略余数）直到第二个数为1为止

（×2就是不断升2的幂的过程，除2求余就是不断二进制转换过程）

如果第二个数是偶数，那么就把他所在行划掉

（二进制对应数位为0，所以不用运算，忽略划掉）

剩下没被划掉的第一列的和就是答案

（进行最后的相加过程）