Count Primes

Leave a comment

November 22, 2016 by oneOokay

Description:

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


技巧想法性的题目吧。。。Prime Numbers:质数,只能被1以及它自身整除的数字。1不是质数。

首先brutal: for -loop对每个int isPrime(int); isPrime(int) 最优解是以下O(根号n).所以总共是O(n^1.5)

public class Solution {
    public int countPrimes(int n) {
        int count = 0;
        for (int i = 1; i < n; i ++){
            if (isPrime(i)){
                count ++;
            }
        }
        return count;
    }
    
    private static boolean isPrime(int num) {
        if (num < 2) return false;
        if (num == 2) return true;
        if (num % 2 == 0) return false;
        for (int i = 3; i * i <= num; i += 2)
        {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

这个更妙:

  • 首先:找到任意一个质数a,把该质数的2-k倍的数(这个数要小于n)都mark为非质数。
  • 用boolean[k]定义为k这个not prime是不是真的。
  • 此时所有的数字not prime都是false;默认所有的数字都是prime数。
  • 接着从i = 2开始:2是最小的质数,从2开始乘以2-k(乘积小于n),mark这些元素为not prime = true。
  • Time complexity: O(nloglogn)
  • Extra memory: O(n)
public class Solution {
    public int countPrimes(int n) {
        int count = 0;
        boolean[] notPrime = new boolean[n];
        for (int i = 2; i < n; i ++){
            if (notPrime[i] == false){
                count ++;
            }
            for (int j = 2; i * j < n; j ++){
                notPrime[i * j] = true;
            }
        }
        return count;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: