[LeetCode] Count Primes

Shisui 发布于2019-08-14 15:54 / 2625人阅读

摘要：用数组标记非质数，每当出现一个为，计数器加一。关于质数有三点大于的质数一定是奇数，如，，奇数中的非质数也一定是奇数的乘积。首先，我们用从到进行标记。标记完所有的合数之后，再用到之间的遍历，所有未被标记的质数。

Problem

Count the number of prime numbers less than a non-negative number, n.

Note

用数组flag标记非质数，每当出现一个flag[i]为false，计数器count加一。
关于质数有三点：

大于3的质数一定是奇数，如3，5，7；

奇数中的非质数也一定是奇数的乘积。

对于一个很大的数n，它的两个因数i和j中一定有一个小于n的开方，所以我们让i <= Math.sqrt(n)，j >= n，这样可以避免重复讨论一些情况。

首先，我们用i从3到Math.sqrt(n)进行标记。
其次，根据上述的第2、3两点，通过乘积i*j对应index的方法对在flag中对合数为index的值赋值true，j+=2，外层一样，i+=2，因为大于3的数中只有奇数有可能是质数，而这些质数i可以通过j的循环标记所有i作为因数的合数。
标记完所有的合数之后，再用Math.sqrt(n)到n之间的遍历，count所有未被标记true的质数。

Solution

public class Solution {
    public int countPrimes(int n) {
        boolean[] mark = new boolean[n];
        if (n <= 2) return 0;
        int i = 3, count = 1; //i from 3, so there is one prime: 2
        while (i <= Math.sqrt(n)) {
            if (!mark[i]) {
                count++;
                int j = i;
                while (i*j < n) {
                    mark[i*j] = true;
                    j += 2;
                }
            }
            i += 2;
        }
        while (i < n) {
            if (!mark[i]) count++;
            i += 2;
        } 
        return count;
    }
}

常规解法

class Solution {
    public int countPrimes(int n) {
        if (n <= 2) return 0;
        boolean[] primes = new boolean[n];
        Arrays.fill(primes, true);
        for (int i = 2; i < n; i++) {
            for (int j = i+i; j < n; j += i) {
                primes[j] = false;
            }
        }
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (primes[i]) count++;
        }
        return count;
    }
}

云服务器 GPU云服务器 Primes LeetCode LeetCode_String leetcode_35_SearchIn

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66096.html

[Leetcode] Count Primes 数素数

摘要：利用这个性质，我们可以建立一个素数数组，从开始将素数的倍数都标注为不是素数。第一轮将等表为非素数，然后遍历到，发现没有被标记为非素数，则将等标记为非素数，一直到为止，再数一遍素数数组中有多少素数。代码将的倍倍倍都标记为非素数 Count Primes Description: Count the number of prime numbers less than a non-nega...

Achilles 2019-08-14 12:28 评论0 收藏0
[LeetCode] 204. Count Primes

Problem Count the number of prime numbers less than a non-negative number, n. Example: Input: 10Output: 4Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7. Solution class Solut...

cheukyin 2019-08-16 13:38 评论0 收藏0
[LintCode/LeetCode] Super Ugly Number

摘要：建两个新数组，一个存数，一个存。数组中所有元素初值都是。实现的过程是，一个循环里包含两个子循环。两个子循环的作用分别是，遍历数组与相乘找到最小乘积存入再遍历一次数组与的乘积，结果与相同的，就将加，即跳过这个结果相同结果只存一次。 Problem Write a program to find the nth super ugly number. Super ugly numbers a...

wuyumin 2019-08-14 15:20 评论0 收藏0
Leetcode[313] Super Ugly Number

摘要：滚动求最大值复杂度考虑一个，的值是下一个可能的替补值。思路数组中保存的是之前保留到的值，因为下一个可能的值是和之前的值的倍数关系。 Leetcode[313] Super Ugly Number Write a program to find the nth super ugly number. Super ugly numbers are positive numbers whos...

Aklman 2019-08-16 10:27 评论0 收藏0
[LintCode/LeetCode] Check Sum of K Primes

Problem Given two numbers n and k. We need to find out if n can be written as sum of k prime numbers. Example Given n = 10, k = 2Return true // 10 = 5 + 5 Given n = 2, k = 2Return false Solution pub...

lakeside 2019-08-16 12:37 评论0 收藏0