牛客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;}

参考答案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;}
};

参考答案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;}}

参考答案Go

package main
import "math"/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param n int整型* @return int整型*/
func primesCount(n int) int {cnt := 0for 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
}

参考答案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;
}