题目描述

给定一个正整数n，请你求出1~n中质数的个数。

样例

输入样例：
8
输出样例：
4

算法

(线性筛) $O(n^2)$

埃拉托瑟尼算法。上网搜。

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
int n,ans;
bool isp[1000010];
void getp(int n){
    for(int i=2;i<=n;i++)if(!isp[i])for(int j=i;j<=n/i;j++)isp[i*j]=true;
}
int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cin>>n;
    getp(n);
    for(int i=2;i<=n;i++)if(!isp[i])ans++;
    std::cout<<ans<<std::endl;
    return 0;
}

C 代码

#include<stdio.h>
int n,ans;
int isp[1000010];
void getp(int n){
    for(int i=2;i<=n;i++)if(isp[i]==0)for(int j=i;j<=n/i;j++)isp[i*j]=1;
}
int main(){
    scanf("%d",&n);
    getp(n);
    for(int i=2;i<=n;i++)if(isp[i]==0)ans++;
    printf("%d",ans);
    return 0;
}

Java 代码

import java.util.*;
class Main{
    static int n;
    static int ans;
    static boolean[]isp=new boolean[1000010];
    static void getp(int n){
        for(int i=2;i<=n;i++)if(!isp[i])for(int j=i;j<=n/i;j++)isp[i*j]=true;
    }
    public static void main(String[]arg){
        Scanner input=new Scanner(System.in);
        n=input.nextInt();
        getp(n);
        for(int i=2;i<=n;i++)if(!isp[i])ans++;
        System.out.print(ans);
    }
}

Python3 代码

isp=[]
for i in range(1000011):
    isp.append(True)
def getp(n):
    for i in range(2,n+1):
        if isp[i]:
            for j in range(i,n//i+1):
                isp[i*j]=False
n=int(input())
getp(n)
ans=0
for i in range(2,n+1):
    if isp[i]:
        ans+=1
print(ans)

Go 代码

package main
import"fmt"
var n,ans int
var isp [1000010]bool
func getp(n int){
    for i:=2;i<=n;i++{
        if(isp[i]==false){
            for j:=i;j<=n/i;j++{
                isp[i*j]=true
            }
        }
    }
}
func main(){
    fmt.Scanf("%d",&n)
    getp(n)
    for i:=2;i<=n;i++{
        if(isp[i]==false){
            ans++;
        }
    }
    fmt.Printf("%d",ans)
}