P751. 素数个数

查看原题

题目描述

给定一个正整数 $n$ ，其中 $n \ge 2$ 。请编程求出区间 $2\sim n$ 中一共有多少个素数。

输入格式

输入一行，一个整数 $n$ 。

输出格式

输出一行，一个整数，表示区间 $2\sim n$ 中素数的个数。

样例

样例 1

输入:

输出:

样例 2

输入:

输出:

数据范围

对于所有数据， $2 \le n \le 50000$ 。

时间限制：1s。

内存限制：128MB。

提示

素数是指大于 $1$ 且只有 $1$ 和它本身两个正因数的整数。

打字区

cc.cc20

00:00 用时 0 CPM 100% 准确率

目标代码 0 / 177

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,z=0;
    cin>>n;
    bool v[50005]={false};
    for(int i=2;i<=n;i++){
        if(!v[i]){
            z++;
            for(int j=i*2;j<=n;j+=i){
                v[j]=true;
            }
        }
    }  
    cout<<z; 
    return 0;
}

输入代码

登录后开始未开始

手速排行榜

正在加载排行榜...

打字量排行榜