课前温习
番外：秦九韶算法
利用秦九韶算法来实现其他进制转十进制的结果求解
下图内容来源：百度百科，侵删。
核心模板
int nToTen(string s,int n){ int ans=0; for(int i=0;i<s.size();i++){ ans=ans*n+s[i]-'0'; } return ans; }
主要代码
#include <iostream> #include <string> using namespace std; string s; int n; //其他进制转十进制（所有进制均适合） /* int nToTen(string s,int n){ int ans=0; for(int i=0;i<s.size();i++){ if(s[i]>='A'&&s[i]<='Z') ans=ans*n+s[i]-'A'+10; else ans=ans*n+s[i]-'0'; } return ans; } */ //其他进制转十进制（仅能处理十进制以下的进制转十进制） int nToTen(string s,int n){ int ans=0; for(int i=0;i<s.size();i++){ ans=ans*n+s[i]-'0'; //可以这样理解：原始答案中一个数都没有，然后把第一个数加了进去，然后每次向答案中加数，都要将原来的答案整体向前移一位，空出位置留给当前位。所以结果就是ans往前移一位的结果再加上当前位的数字 } return ans; } int main(){ cin>>n; cin>>s; cout<<nToTen(s,n); return 0; }
一、质数
（“就被称为质数”）
1. 试除法判定质数
小于x的约数是成对出现的（d和x/d），所以不需要从2枚举到n-1，只需要每次枚举较小的约数即可。即每次枚举从i到x/i。
核心模板
普通版
bool is_prime(int x){ if(x<2) return false; for(int i=2;i<=x/i;i++){ if(x%i==0){ return false; } } return true; }
优化版
bool is_prime(int x){ if(x<=3) return x>1; if(x%6!=1&&x%6!=5) return false; for(int i=5;i<=x/i;i+=6){ if(x%i==0&&x%(i+2)==0) return false; } return true; }
题目链接：
866. 试除法判定质数
1.1题目描述
给定 n 个正整数 ai，判定每个数是否是质数。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个正整数 ai。
输出格式
共 n 行，其中第 i 行输出第 i 个正整数 ai 是否为质数，是则输出 Yes，否则输出 No。
数据范围
1≤n≤100,1≤ai≤231−1
输入样例：
2 2 6
输出样例：
Yes No
1.2思路分析
套用模板即可，注意细节。
1.3代码实现
#include <iostream> using namespace std; const int N=110; int a[N]; int n; bool is_p(int n){ if(n<2) return false; for(int i=2;i<=n/i;i++){ if(n%i==0) return false; } return true; } int main(){ cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; if(is_p(a[i])) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }
2、试除法分解质因数
下图内容来源：百度百科，侵删。
思路：
下图内容来源这里，侵删。
核心模板
void divide(int x){ for(int i=2;i<=x/i;i++){ if(x%i==0){ int s=0; while(x%i==0) x/=i,s++; cout<<i<<' '<<s<<endl; } } if(x>1) cout<<x<<' '<<1<<endl; cout<<endl; }
题目链接：867. 分解质因数
1.4题目描述
给定 n 个正整数 ai ，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个正整数 ai。
输出格式
对于每个正整数 ai，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。
每个正整数的质因数全部输出完毕后，输出一个空行。
数据范围
1≤n≤100,2≤ai≤2×109
输入样例：
2 6 8
1
2
3
输出样例：
2 1 3 1 2 3
1.5思路分析
套用模板即可，注意细节。
1.6代码实现
#include <iostream> using namespace std; int n; void divide(int n){ for(int i=2;i<=n/i;i++){ if(n%i==0){ int s=0; while(n%i==0){ n/=i; s++; } cout<<i<<' '<<s<<endl; } } if(n>1) cout<<n<<' '<<1<<endl; cout<<endl; } int main(){ cin>>n; while(n--){ int a; cin>>a; divide(a); } return 0; }
二、筛素数
1.朴素筛法求素数
从2到n枚举每个数，删掉其所有的倍数，枚举完之后，没有被删掉的数为质数。
核心模板
int primes[N],cnt; //primes[]存储所有素数 bool st[N]; //st[x]存储x是否被筛掉 void get_primes(int n){ st[0]=st[1]=true; //0和1均不是质数 for(int i=2;i<=n;i++){ if(st[i]) continue; primes[cnt++]=i; for(int j=i+i;j<=n;j+=i){ st[j]=true; } } }
埃氏筛法
int primes[N],cnt; //primes[]存储所有素数 bool st[N]; //st[x]存储x是否被筛掉 void get_primes(int n){ st[0]=st[1]=true; //0和1均不是质数 for(int i=2;i<=n;i++){ if(!st[i]){ primes[cnt++]=i; for(int j=i+i;j<=n;j+=i){ st[j]=true; } } } }
2.线性筛法求素数（O(n)）
核心模板
int primes[N],cnt; //primes[]存储所有素数 bool st[N]; //st[x]存储x是否被筛掉 void get_primes(int n){ st[0]=st[1]=true; //0和1均不是质数 for(int i=2;i<=n;i++){ if(!st[i]) primes[cnt++]=i; for(int j=0;primes[j]<=n/i;j++){ st[primes[j]*i]=true; if(i%primes[j]==0) break; } } }
题目链接：868. 筛质数
2.1题目描述
给定一个正整数 n，请你求出 1∼n 中质数的个数。
输入格式
共一行，包含整数 n。
输出格式
共一行，包含一个整数，表示 1∼n 中质数的个数。
数据范围
1≤n≤106
输入样例：
8
输出样例：
4
2.2思路分析
利用上述模板即可。
2.3代码实现
埃氏筛法
#include <iostream> using namespace std; const int N=1000010; int n,cnt; int primes[N]; bool st[N]; void getPrimes(int n){ for(int i=2;i<=n;i++){ if(!st[i]){ primes[cnt++]=i; for(int j=i+i;j<=n;j+=i){ st[j]=true; } } } } int main(){ cin>>n; getPrimes(n); cout<<cnt; return 0; }
线性筛法
#include <iostream> using namespace std; const int N=1000010; int n,cnt; int primes[N]; bool st[N]; void getPrimes(int n){ for(int i=2;i<=n;i++){ if(!st[i]) primes[cnt++]=i; for(int j=0;primes[j]<=n/i;j++){ st[i*primes[j]]=true; if(i%primes[j]==0) break; //此时primes[j]一定是i的最小质因子 } } } int main(){ cin>>n; getPrimes(n); cout<<cnt; return 0; }
