牛客NC368 质数的计数【中等 基础数学，数论 C++/Java/Go/PHP】

题目

题目链接：
https://www.nowcoder.com/practice/190167d1990442da9adb133980259a27

思路

判断x是否是质数：这是判断质数最好的代码了
   public boolean isPrime(int x){
        if(x ==2 || x==3) return true;
        if(x%6!=1 && x%6!=5) return false; //不在6倍数的两边肯定不是质数

        int sqrt = (int)Math.sqrt(x);


        for (int i = 5; i <=sqrt ; i+=6) {
            //如果在6的倍数两边，但是n%i==0 或者 n%(i+2)==0 也不是质数
            if(x%i==0 || x%(i+2) ==0) return false;
        }

        return true;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

参考答案C++

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    int primesCount(int n) {
        int cnt = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime(i))
                cnt++;
        }
        return cnt;
    }

    bool  isPrime(int x) {
        if (x == 2 || x == 3) return true;
        if (x % 6 != 1 && x % 6 != 5) return false; //不在6的两边肯定不是质数
        int st = sqrt(x);
        for (int i = 5; i <= st; i++) {
            //如果在6的两边，但是n%i==0 或者 n%(i+2)==0 也不是质数
            if (x % i == 0 || x % (i + 2) == 0) return false;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

参考答案Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    public int primesCount (int n) {
        int cnt = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime(i)) cnt++;
        }

        return cnt;
    }

    public boolean isPrime(int x) {
        if (x == 2 || x == 3) return true;
        if (x % 6 != 1 && x % 6 != 5) return false; //不在6的两边肯定不是质数

        int sqrt = (int)Math.sqrt(x);

        for (int i = 5; i <= sqrt ; i += 6) {
            //如果在6的两边，但是n%i==0 或者 n%(i+2)==0 也不是质数
            if (x % i == 0 || x % (i + 2) == 0) return false;
        }

        return true;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

参考答案Go

package main
import "math"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param n int整型
 * @return int整型
 */
func primesCount(n int) int {
		cnt := 0
	for i := 2; i < n; i++ {
		if isPrime(i) {
			cnt++
		}

	}
	return cnt
}

func isPrime(x int) bool {
	if x == 2 || x == 3 {
		return true
	}

	if x%6 != 1 && x%6 != 5 {
		return false //不在6的两边肯定不是质数
	}

	sqrt := int(math.Sqrt(float64(x)))

	for i := 5; i <= sqrt; i += 6 {
		//如果在6的两边，但是n%i==0 或者 n%(i+2)==0 也不是质数
		if x%i == 0 || x%(i+2) == 0 {
			return false
		}
	}
	return true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

参考答案PHP

<?php


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @return int整型
 */
function primesCount( $n )
{
       $cnt =0;
    for($i=2;$i<$n;$i++){
        if(isPrime($i))
            $cnt++;
    }
    return $cnt;
}


function isPrime($x){
    if($x ==2 || $x ==3) return true;
    if($x %6!=1 && $x%6!=5) return false; //不在6的两边肯定不是质数
    $sqrt = intval(sqrt($x));
    for($i=5;$i<=$sqrt;$i++){
        //如果在6的两边，但是n%i==0 或者 n%(i+2)==0 也不是质数
        if($x%$i ==0 || $x%($i+2) ==0)
            return false;
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32