首页 > 代码库 > leetcode 204. Count Primes 找出素数的个数 ---------- java
leetcode 204. Count Primes 找出素数的个数 ---------- java
Description:
Count the number of prime numbers less than a non-negative number, n.
找出小于n的素数个数。
1、用最淳朴的算法果然超时了。
public class Solution { public int countPrimes(int n) { if (n < 2){ return 0; } int result = 0; for (int i = 2; i < n; i++){ if (isPrimes(i)){ result++; } } return result; } public boolean isPrimes(int num){ for (int i = 2; i <= Math.sqrt(num); i++){ if (num % i == 0){ return false; } } return true; } }
2、埃拉托斯特尼筛法Sieve of Eratosthenes
我们从2开始遍历到根号n,先找到第一个质数2,然后将其所有的倍数全部标记出来,然后到下一个质数3,标记其所有倍数,一次类推,直到根号n,此时数组中未被标记的数字就是质数。我们需要一个n-1长度的bool型数组来记录每个数字是否被标记,长度为n-1的原因是题目说是小于n的质数个数,并不包括n。
public class Solution { public int countPrimes(int n) { boolean[] isPrime = new boolean[n]; for (int i = 2; i < n; i++) { isPrime[i] = true; } for (int i = 2; i * i < n; i++) { if (!isPrime[i]) continue; for (int j = i * i; j < n; j += i) { isPrime[j] = false; } } int count = 0; for (int i = 2; i < n; i++) { if (isPrime[i]) count++; } return count; } }
leetcode 204. Count Primes 找出素数的个数 ---------- java
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。