首页 > 代码库 > Leetcode_204_Count Primes
Leetcode_204_Count Primes
本文是在学习中的总结。欢迎转载但请注明出处:http://blog.csdn.net/pistolove/article/details/46366207
Description:
Count the number of prime numbers less than a non-negative number, n.
思路:
(1)题意为给定整数n,求解n以内的整数中有多少个素数(质数)。
(2)该题涉及到数学相关的知识。首先。看下素数的定义:质数(prime number)又称素数,有无限个。一个大于1的自然数,除了1和它本身外,不能被其它自然数(质数)整除,换句话说就是该数除了1和它本身以外不再有其它的因数;否则称为合数(来自百度百科);其次,对于100以内的数字。发现一下规律:不被2、3、5整数的数是质数,可是超过100就不成立了,比如像11*11=121这种数,就须要对其能否开方进行判定。最后。这里通过排除法进行操作,将n以内大于2的数所有存入布尔数组,并将其布尔值值为true,然后进行遍历,在遍历过程中,假设遍历的数值为false。则continue;否则,则从当前下标開始。对当前下标值的平方是否在n范围内进行判定,假设在则将当前下标值置为false,直到遍历结束。最后所得数值中值为true的个数即为素数的个数。
(3)详情见下方代码。
希望本文对你有所帮助。该代码为Lettcode官网上的代码,非本人所写。但有必要学习下。
算法代码实现例如以下:
/** * * @author liqqc * */ public class Count_Primes { public int countPrimes(int n) { boolean[] isPrime = new boolean[n]; for (int i = 2; i < n; i++) { isPrime[i] = true; } // Loop‘s ending condition is i * i < n instead of i < sqrt(n) // to avoid repeatedly calling an expensive function sqrt(). for (int i = 2; i * i < n; i++) { if (!isPrime[i]) continue; for (int j = i * i; j < n; j += i) { isPrime[j] = false; } } int count = 0; for (int i = 2; i < n; i++) { if (isPrime[i]){ count++; } } return count; } }
Leetcode_204_Count Primes
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。