返回小于 N 的质数个数

[编程题]返回小于 N 的质数个数

热度指数：4576 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

请考虑性能

输入描述:

一个整数N

输出描述:

小于N的质数数量

示例1

输入

输出

说明

N=10，质数有 [2, 3, 5, 7]

备注:

0、1 不属于质数。

算法知识视频讲解

小谷围做题家

package main

import (
    "fmt"
)

func main() {
    var n int
    fmt.Scan(&n)
    ans:=0
    for i:=2;i<n;i++{
        if check(i){
            ans++
        }
    }
    fmt.Print(ans)
}

func check(x int)bool{
    if x==2{
        return true
    }
    if x>2&&x%2==0{
        return false
    }
    for i:=3;i<x;i+=2{
        if x%i==0{
            return false
        }
    }
    return true
}

发表于 2023-03-19 08:35:53 回复(0)