欧拉函数

#include <bits/stdc++.h>
using namespace std;
int cnt = 0;
int vis[100000];
int prim[100000];
int n = 100;
int main()
{
    memset(vis, 0, sizeof vis);
    memset(prim, 0, sizeof prim);
    for (int i = 2; i <= n; i++)
    {
        if (vis[i] == 0)
        {
            prim[++cnt] = i;
        }
        for (int j = 1; j <= cnt && i * prim[j] <= n; j++)
        {
            vis[i * prim[j]] = 1;
            if (i % prim[j] == 0)
            {
                break;
            }
        }
    }
    for (int i = 0; i < cnt; i++)
    {
        cout << prim[i] << " ";
    }
    return 0;
}

全篇的精华在于：

if(i % prim[j] == 0) break;

#include 
using namespace std;
vector pri;
const int MAXX = 100;
vector vis(100);
int main(){
    int n;
    cin>>n;
    vis.resize(n+10);
    for (int i = 2;i<=n;i++){
        if(vis[i]==0){
            pri.push_back(i);
        }
        for (int j = 0;j<=pri.size()&&i * pri[j]<=n;j++){
            vis[i*pri[j]]=1;
            if (i%pri[j]==0){
                break;
            }
        }
    }
    // for (auto v:pri){
    //     cout<