3 条题解

  • 0
    @ 2025-4-21 18:37:00

    #include<bits/stdc++.h> using namespace std; const int N = 50000010; bool isp[N]; vector prime; void eulerPrime(int n) { memset(isp, true, sizeof(isp)); isp[0] = isp[1] = false; for (int i = 2; i <= n; i++) { if (isp[i]) prime.push_back(i); for (int p : prime) { if (i * p > n) break; isp[i * p] = false; if (i % p == 0) break; } } }

    int main(){ int n; cin>>n;

    eulerPrime(n);
    cout<<prime.size();
    return 0;
    

    }

    • 0
      @ 2024-2-17 15:14:40

      欧拉筛AC

      #include<bits/stdc++.h>
      #pragma GCC optimize(3)
      #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
      using namespace std;
      const int N=1e7+10;
      const int INF=0x3f3f3f3f;
      int p[N],n,cnt;
      bool f[N];
      int main()
      {
      	IOS;
      	cin>>n;
      	for(int i=2;i<=n;++i)
      	{
      		if(!f[i])
      		{
      			p[++cnt]=i;
      		}
      		for(int j=1;j<=cnt && i*p[j]<=n;++j)
      		{
      			f[i*p[j]]=1;
      			if(i%p[j]==0)break;
      		}
      	} 
      	cout<<cnt;
          return 0;
      }
      
      
      • 0
        @ 2023-10-23 20:41:28

        初学者勿做,要用筛法

        #include <bits/stdc++.h>
        using namespace std;
        const int maxn=1e7;
        bool is[maxn+10];
        int sum,n;
        int main(){
         cin>>n;
            memset(is,0,sizeof is);
            is[1]=1;
            for(int i=2;i<=maxn;i++){
                for(int j=2;i*j<=maxn;j++){
                    is[i*j]=1;
                }
            }
            cin>>n;
            for(int i=1;i<=n;i++){
                if(is[i]==0)
                    sum++;
            }
            cout<<sum;
            return 0;
        }
        
        • 1

        信息

        ID
        1836
        时间
        1000ms
        内存
        256MiB
        难度
        8
        标签
        递交数
        209
        已通过
        39
        上传者