当前位置: 代码迷 >> 综合 >> JAVA算法:统计小于给定整数N的素数的个数
  详细解决方案

JAVA算法:统计小于给定整数N的素数的个数

热度:8   发布时间:2024-01-15 19:39:31.0

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--;