问题标题: 酷町堂：6605

题目描述 Description

给定N，求1，2,…,N中素数的个数

输入描述 Input Description

一行：一个整数N

输出描述 Output Description

一行：一个整数表示素数的个数

样例输入 Sample Input

10

样例输出 Sample Output

4

数据范围及提示 Data Size & Hint

对于40% 的数据，1≤N≤106
对于 80% 的数据，1≤N≤107
对于 100% 的数据1≤N≤108

80分超时代码

思路：按素数的思路来的

#include<bits/stdc++.h>
using namespace std;
int n,sum=0,a[10000000];
int main(){
    cin>>n;
    for(int i=2;i<=n;i++){
        if(a[i]==0){
            for(int j=2*i;j<=n;j+=i){
                if(a[j]!=1){
                    a[j]=1;
                    sum++;
                }
            }
        }
    }
    cout<<n-sum-1;
    return 0;
}

朱小川在2021-12-14 19:20:50追加了内容

1

朱小川在2021-12-15 13:47:28追加了内容

一个新的80分超时代码

#include<bits/stdc++.h>
using namespace std;
int sum=1;
int n;
int main(){
    cin>>n;
    if(n<2){
        cout<<0<<endl;
        return 0;
    }
    for(int i=3; i<=n; i+=2){
        int t=int(sqrt(i));
        int flag=0;
        for(int j=3; j<=t; j+=2){
            if(i%j==0){
                flag=1;
                break;
            }
        }
        if(!flag) sum++;
    }
    cout<<sum;
    return 0;
}

朱小川在2021-12-16 18:56:25追加了内容

d

朱小川在2021-12-19 20:48:17追加了内容

1

朱小川在2022-01-03 20:56:51追加了内容

1