素数:大于1的整数中,只能被1和这个数本身整除的数.

1.判断质数

试除法判断质数:试除法也就是从2开始,到n-1结束,判断有没有能整除n的数,如果有,则不是质数;反之则是质数.在判断过程中,一个可以优化判断范围(如果一个数能被整除,那么两个因子中的其中一个因子一定小于根号n,,也就是说,判断范围能缩小到根号n之前,并且包括根号n).利用反证法证明一下上述观点,如果存在因子并且大于根号n,那么两者相乘一定会大于n,因为根号n和根号n相乘就是n,更不要说两者都大于根号n的情况了.另一个则是将试除法写成函数的形式,去调用来解决问题,这样当一个数不是素数的时候,直接返回,从而减少一些变量的定义和一些思维的转换.

给大家上代码:
 

# include <iostream>using namespace std;bool panduan(int x)
{if(x<2)   return 0;for(int i=2;i<=x/i;i++){if(x%i==0)   return 0;}return 1;
}int main()
{int n;cin>>n;while(n--){int x;cin>>x;if(panduan(x))   cout<<"Yes"<<endl;else   cout<<"No"<<endl;}return 0;
}

2.筛法求素数

所谓筛法,其实就是将一段区间的素数求解出来,试除法针对的是某一个素数.

筛法的基本原理,举例子来说明,求1到10之间的素数,先定义一个数组,存放素数;再定义一个bool类型的数组,表示此数是什么数,如果是素数,则为0,反之则为1.先从2开始判断,其为0,表示是素数,然后对于2的倍数的数,都删除.......直到最后

朴素筛法

朴素筛法和所说的筛法基本原理一样,直接给大家写一下代码吧.

# include <iostream>using namespace std;int cnt;
int a[100010];
bool st[1000010];void init(int n)
{for(int i=2;i<=n;i++){if(st[i]==0)a[cnt++]=i;for(int j=i;j<=n;j+=i)st[j]=1;}
}int main()
{int n;cin>>n;init(n);cout<<cnt;return 0;
}

埃氏筛法

埃氏筛法是对朴素筛法的优化,其优化的地方是:当一个数是素数之后,就将其的倍数筛去,而不是朴素筛法中,无论是不是素数,都将其的倍数筛去.对于2来说,将其倍数筛去以后,4的倍数也是2的倍数,不用再筛,而朴素筛法依旧会筛,增加了时间复杂度.

代码呈上:
 

# include <iostream>using namespace std;int cnt;
int a[100010];
bool st[1000010];void init(int n)
{for(int i=2;i<=n;i++){if(st[i]==0){a[cnt++]=i;for(int j=i;j<=n;j+=i){st[j]=1;}}}
}int main()
{int n;cin>>n;init(n);cout<<cnt;return 0;
}

线性筛法

线性筛法是筛法中最好的优化,就不做太多的解释,直接给大家上一下板子吧.

# include <iostream>using namespace std;int cnt;
int a[100010];
bool st[1000010];void init(int n)
{for(int i=2;i<=n;i++){if(st[i]==0)a[cnt++]=i;for(int j=0;a[j]*i<=n;j++){st[a[j]*i]=1;if(i%a[j]==0)   break;}}
}int main()
{int n;cin>>n;init(n);cout<<cnt;return 0;
}

3.分解质因数

对于任意一个合数,都可以分解成几个质数相乘的形式.其实没啥可说的,直接上代码吧.

# include <iostream>using namespace std;int main ()
{int t;cin>>t;while(t--){int n;cin>>n;for(int i=2;i<=n/i;i++){if(n%i==0){int sum=0;while(n%i==0){sum++;n/=i;}cout<<i<<" "<<sum<<endl;}}if(n>1)   cout<<n<<" 1"<<endl;cout<<endl;}return 0;
}