Description

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

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Analysis

It is easy to come up with the brute force method. When judging a prime number, we need to judge if there is a divisor of n from $$2$$ to $$\sqrt{n}$$. So the time complexity is $$O(n\sqrt{n})$$.

However, we have a efficient method, Sieve of Eratosthenes. We define a boolean vector that reflects whether the number is prime. Set the initial values be true. For the number from $$2$$ to $$n-1$$, if one number is true, then set the multiples of it be false. In the meantime, count the number that is true.

Solution

class Solution {
public int countPrimes(int n) {
if(n<=2) return 0;
int res=0;
boolean[] pri=new boolean[n-2];
for(int i=2;i<n;i++)
{
pri[i-2]=true;
}
for(int i=2;i<n;i++)
{
if(pri[i-2]==true)
{
res++;
for(int j=2;i*j<n;j++)
pri[i*j-2]=false;
}
}
return res;
}
}


Reference

[1] https://github.com/EdwardShi92/Leetcode-Solution-Code/blob/master/CountPrimes.java
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 1, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "http://ningziwen.com/2018/08/12/count-primes/", "fetch_time": 1568896352000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2019-39/segments/1568514573519.72/warc/CC-MAIN-20190919122032-20190919144032-00332.warc.gz", "warc_record_offset": 135043408, "warc_record_length": 6829, "token_count": 321, "char_count": 1079, "score": 3.703125, "int_score": 4, "crawl": "CC-MAIN-2019-39", "snapshot_type": "latest", "language": "en", "language_score": 0.6506894826889038, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00042-of-00064.parquet"}