10.26-东塘404-J1R(2):埃氏筛

pico_fence · 2025-11-02 19:14:23 · 个人记录

新知识

//埃氏筛：
//标记当前数是合数(1)/质数(0)
//默认一开始所有数都是指数
bool isp[100000010];
void ashpick(int n){  //筛出1~n之间的所有数
  isp[0]=isp[1]=1;  //0和1都不是质数
  for(int i=1;i<=n;i++){
    if(isp[i]==0){  //找到一个质数i
      for(int j=i*2;j<=n;j+=i){  //拿i去筛掉他的所有倍数
        isp[j]=1;  //标记成不是质数
      }
    } 
  } 
} 

P8754 [蓝桥杯 2021 省 AB2] 完全平方数

思路

先定义个n变量，要开long long，在输入n,然后定个x=1,来存最小的正整数，再来一个for循环：

for(int i=2;i<=n/i;i++){
  int cnt=0;
  while(n%i==0){
    cnt++;
    n/=i;
  }
  if(cnt%2==1){
    x*=i;       
  }
}

然后来个if判断：if(n>1)x*=n; 最后输出x。

代码

#include<bits/stdc++.h>
using namespace std;
long long n;
int main(){
    cin>>n;
    long long x=1;
    for(int i=2;i<=n/i;i++){
        int cnt=0;
        while(n%i==0){
            cnt++;
            n/=i;
        }
        if(cnt%2==1){
            x*=i;       
        }
    }
    if(n>1)x*=n;
    cout<<x;
    return 0;
} 

P10495 阶乘分解

思路

先顶一个变量和一个数组：n,cnt[1000010]；然后输入n,最后来两个for循环：

for(int xx=1;xx<=n;xx++){
    int x=xx;
    for(int i=2;i<=x/i;i++){
        while(x%i==0){
            cnt[i]++;
            x/=i;
        }
    }
    if(x>1)cnt[x]++;
}
for(int i=1;i<=1000000;i++){
    if(cnt[i]){
        cout<<i<<' '<<cnt[i]<<endl;
    }
}

代码

#include<bits/stdc++.h>
using namespace std;
long long n,cnt[1000010];
int main(){
    cin>>n;
    for(int xx=1;xx<=n;xx++){
        int x=xx;
        for(int i=2;i<=x/i;i++){
            while(x%i==0){
                cnt[i]++;
                x/=i;
            }
        }
        if(x>1)cnt[x]++;
    }
    for(int i=1;i<=1000000;i++){
        if(cnt[i]){
            cout<<i<<' '<<cnt[i]<<endl;
        }
    }
    return 0;   
}

B4170 [BCSP-X 2024 6 月小学高年级组] 最小质因子

思路

先定一个判断质数因数的函数：is_prime(),在创建一个t，然后关闭同步流，最后来个while循环：

while(t--){
        long long n;
        cin>>n;
        if(is_prime(n)){
            cout<<n<<endl;
            continue;
        }
        for(long long i=2;i<=n/i;i++){
            if(n%i==0){
                cout<<i<<endl;
                break;
            }
        }
    }

代码

#include<bits/stdc++.h>
using namespace std;
long long is_prime(long long n){
  if(n<=1){
    return 0;
  }
  for(long long i=2;i<=n/i;i++){
    if(n%i==0){
      return 0;
    }
  }
  return 1;
}
long long t; 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--){
        long long n;
        cin>>n;
        if(is_prime(n)){
            cout<<n<<endl;
            continue;
        }
        for(long long i=2;i<=n/i;i++){
            if(n%i==0){
                cout<<i<<endl;
                break;
            }
        }
    }
    return 0;
}

P3912 素数个数

先定义个埃氏筛函数，再定个n,输入n,再用埃氏筛函数(n),再定个 ans,然后来个for循环，最后输出ans;

代码

#include<bits/stdc++.h>
using namespace std;
bool isp[100000000];
void ashpick(int n){
  isp[0]=isp[1]=1;
  for(int i=2;i<=n;i++){
    if(isp[i]==0){
        for(int j=i*2;j<=n;j+=i){
            isp[j]=1;
        }   
    }
  }
}
long long n;
int main(){
    cin>>n;
    ashpick(n);
    long long ans=0;
    for(int i=1;i<=n;i++){
        if(isp[i]==0)ans++;
    }
    cout<<ans;
    return 0;
}