JAVA算法:统计小于给定整数N的素数的个数
问题描述
给你一个正整数n,统计小于n的素数的个数。
例如:当 n=10时,输出结果为4。
因为小于整数10的素数有2,3,5,7;一共4个素数。
问题分析
算法设计
package com.bean.algorithm.basic;public class CountPrimesLessthanN {public static int countPrimes(int n) {if (n == 0 || n == 1)return 0;int[] primes = new int[n];int res = n - 2;// 1 => not prime// 0 => prime// initially all the elements are prime// marking 0 and 1 as non-primeprimes[0] = 1;primes[1] = 1;for (int i = 2; i < n; i++) {// if the current element is primeif (primes[i] == 0) {for (int j = 2; i * j < n; j++) {// mark all the fators of current prime as non-primeif (primes[i * j] != 1) {primes[i * j] = 1;res--;