NC716 牛牛与素数(2)（四种语言+视频讲解）

- 题目描述：

- 题目链接：
https://www.nowcoder.com/practice/1033cb51ef754f25aefd8057b534286c?

- 设计思想：

-视频讲解链接B站视频讲解
- 复杂度分析：

- 代码：
c++版本:

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定一个数字n，返回[7,n)内有多少素数。
     * @param n int整型 代表题目中的n
     * @return int整型
     */
    //埃氏筛法
    int prime[1000005];  //第i个素数
    bool is_prime[1000005];  //is_prime[i]为true时表示i是素数
    //返回n以内素数的个数
    void sieve(int n){
        int p = 0;
        for(int i = 0; i <= n; i++) is_prime[i] = true;
        is_prime[0] = is_prime[1] = false;//0和1不是素数
        for(int i = 2; i <= n; i++){
            if(is_prime[i]){
                prime[p++] = i;
                for(int j = 2*i; j <= n; j+=i) is_prime[j] = false;  //筛去所有素数的倍数
            }
        }
    }
    int solve(int n) {
        // write code here
        sieve(n);//进行筛素数
        int res = 0;
        //找[7,n)的素数
        for(int i = 7;i < n;i ++){
            if(is_prime[i])
                res ++;
        }
        return res;
    }
};

Java版本：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定一个数字n，返回[7,n)内有多少素数。
     * @param n int整型 代表题目中的n
     * @return int整型
     */
    //埃氏筛法
    public int [] prime = new int [1000005];  //第i个素数
    public boolean[] is_prime = new boolean[1000005];  //is_prime[i]为true时表示i是素数
    //返回n以内素数的个数
    public void sieve(int n){
        int p = 0;
        for(int i = 0; i <= n; i++) is_prime[i] = true;
        is_prime[0] = is_prime[1] = false;//0和1不是素数
        for(int i = 2; i <= n; i++){
            if(is_prime[i]){
                prime[p++] = i;//标记素数是谁
                for(int j = 2*i; j <= n; j+=i) is_prime[j] = false;  //筛去所有素数的倍数
            }
        }
    }
    public int solve(int n) {
        // write code here
        sieve(n);//进行筛素数
        int res = 0;
        //找[7,n)的素数
        for(int i = 7;i < n;i ++){
            if(is_prime[i])
                res ++;
        }
        return res;
    }
}

Python版本:

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 给定一个数字n，返回[7,n)内有多少素数。
# @param n int整型 代表题目中的n
# @return int整型
#
prime = [0]* 1000005#第i个素数
is_prime = [(True)]*1000005#is_prime[i]为true时表示i是素数
class Solution:
    #埃氏筛法
    #返回n以内素数的个数
    def sieve(self,n):
        p = 0
        is_prime[0] = is_prime[1] = False#0和1不是素数
        for i in range(2,n+1):
            if is_prime[i]:
                prime[p] = i#标记素数是谁
                p += 1
                for j in range(2*i,n + 1,i): is_prime[j] = False#筛去所有素数的倍数
    def solve(self , n ):
        # write code here
        self.sieve(n)#进行筛素数
        res = 0
        #找[7,n)的素数
        for i in range(7,n):
            if is_prime[i]:
                res += 1
        return res

JavaScript版本:

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 给定一个数字n，返回[7,n)内有多少素数。
 * @param n int整型 代表题目中的n
 * @return int整型
 */
//埃氏筛法
let prime = new Array();  //第i个素数
let is_prime = new Array();  //is_prime[i]为true时表示i是素数
//返回n以内素数的个数
function sieve(n){
    let p = 0;
    for(let i = 0; i <= n; i++) is_prime[i] = true;
        is_prime[0] = is_prime[1] = false;//0和1不是素数
        for(let i = 2; i <= n; i++){
            if(is_prime[i]){
                prime[p++] = i;//标记素数是谁
                for(let j = 2*i; j <= n; j+=i) is_prime[j] = false;  //筛去所有素数的倍数
            }
        }
    }
function solve( n ) {
    // write code here
        sieve(n);//进行筛素数
        let res = 0;
        //找[7,n)的素数
        for(let i = 7;i < n;i ++){
            if(is_prime[i])
                res ++;
        }
        return res;

}
module.exports = {
    solve : solve
};