启蒙阶段常用算法技巧（续）

判断质数

判断是否是质数的代价不平衡，则先假设难判断的情况为真

• 是质数：从2到n-1所有数字都不能整除（困难）
• 不是质数：从2到n-1存在能整除的数（容易）
• 先假设是质数，再反证不是质数

int n;
cin>>n;
if(n<2){
    cout<<"no"; // 排除特殊情况
    return 0;
}
bool f=true; // 创建一个标记，假设n是质数
for(int i=2;i<n;i++) {
   if(n%i==0){
       f=false; // 发现整除，修改标记
       break;
   } 
}
if(f){
    cout<<"yes";
}
else{
    cout<<"no";
}
return 0;

分解质因数

从2开始枚举所有质数，判断是否能整除n

• 如果能整除，改变n值重新判断
• 如果不能整除，除数递增
• 直到n变为1

int n;
cin>>n;
if(n<2){
    cout<<n; // 排除特殊情况
    return 0;
}
int t=2;
while(n!=1){
    while(n%t==0){
        cout<<t<<" ";
        n=n/t;
    }
    t++;
}

水仙花数

水仙花数是指一个3位数，其各位数字的3次幂之和等于它本身的数字。

• 先把每个数字拆分成个位、十位、百位
• 再利用水仙花数特点公式判断是否符合要求

for(int i=100;i<=999;i++){
    int g=i%10;
    int s=i/10%10;
    int b=i/100;
    if(g*g*g+s*s*s+b*b*b == i){
        cout<<i<<" ";
    }
}

阶乘和

先计算出n的阶乘，再列出前n项，每个n的阶乘，最后做累加

int n;
cin>>n;
// 计算出n的阶乘
int s=1;
for(int i=1;i<=n;i++){
    s=s*i; 
}
cout<<s; // n的阶乘

int n;
cin>>n;
// 计算出每个1～n之间的数的阶乘
for(int t=1;t<=n;t++){
    int s=1;
    for(int i=1;i<=t;i++){
        s=s*i; 
    }
    cout<<s<<" "; // t的阶乘
}

// 最终求和
int n;
cin>>n;
int ans=0; // 累加初始值
for(int t=1;t<=n;t++){
    // 计算出n的阶乘
    int s=1;
    for(int i=1;i<=t;i++){
        s=s*i; 
    }
    ans=ans+s; // 累加各个阶乘值
}
cout<<ans;

// 进阶版本
int n;
cin>>n;
int ans=0; // 累加初始值
int s=1;
for(int t=1;t<=n;t++){
    s=s*t; // 阶乘
    ans=ans+s; // 阶乘和
}
cout<<ans;

星阵问题

输入n，输出n*n的特定星阵图

int n;
cin>>n;
for(int i=1;i<=n;i++){ // 外层循环确定打印几行
    for(int j=1;j<=i;j++){ // 内层循环确定每行打印的内容
        cout<<"*"; // 根据条件确定具体细节
    }
    cout<<endl;
}

常用星阵图像条件

• 对角线：i==j||i+j==n+1
• 上下边界：i==1||i==n
• 左右边界：j==1||j==n