摘要:用数组标记非质数,每当出现一个为,计数器加一。关于质数有三点大于的质数一定是奇数,如,,奇数中的非质数也一定是奇数的乘积。首先,我们用从到进行标记。标记完所有的合数之后,再用到之间的遍历,所有未被标记的质数。
Problem
Count the number of prime numbers less than a non-negative number, n.
Note用数组flag标记非质数,每当出现一个flag[i]为false,计数器count加一。
关于质数有三点:
大于3的质数一定是奇数,如3,5,7;
奇数中的非质数也一定是奇数的乘积。
对于一个很大的数n,它的两个因数i和j中一定有一个小于n的开方,所以我们让i <= Math.sqrt(n),j >= n,这样可以避免重复讨论一些情况。
首先,我们用i从3到Math.sqrt(n)进行标记。
其次,根据上述的第2、3两点,通过乘积i*j对应index的方法对在flag中对合数为index的值赋值true,j+=2,外层一样,i+=2,因为大于3的数中只有奇数有可能是质数,而这些质数i可以通过j的循环标记所有i作为因数的合数。
标记完所有的合数之后,再用Math.sqrt(n)到n之间的遍历,count所有未被标记true的质数。
public class Solution { public int countPrimes(int n) { boolean[] mark = new boolean[n]; if (n <= 2) return 0; int i = 3, count = 1; //i from 3, so there is one prime: 2 while (i <= Math.sqrt(n)) { if (!mark[i]) { count++; int j = i; while (i*j < n) { mark[i*j] = true; j += 2; } } i += 2; } while (i < n) { if (!mark[i]) count++; i += 2; } return count; } }
常规解法
class Solution { public int countPrimes(int n) { if (n <= 2) return 0; boolean[] primes = new boolean[n]; Arrays.fill(primes, true); for (int i = 2; i < n; i++) { for (int j = i+i; j < n; j += i) { primes[j] = false; } } int count = 0; for (int i = 2; i < n; i++) { if (primes[i]) count++; } return count; } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/66096.html
摘要:利用这个性质,我们可以建立一个素数数组,从开始将素数的倍数都标注为不是素数。第一轮将等表为非素数,然后遍历到,发现没有被标记为非素数,则将等标记为非素数,一直到为止,再数一遍素数数组中有多少素数。代码将的倍倍倍都标记为非素数 Count Primes Description: Count the number of prime numbers less than a non-nega...
Problem Count the number of prime numbers less than a non-negative number, n. Example: Input: 10Output: 4Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7. Solution class Solut...
摘要:建两个新数组,一个存数,一个存。数组中所有元素初值都是。实现的过程是,一个循环里包含两个子循环。两个子循环的作用分别是,遍历数组与相乘找到最小乘积存入再遍历一次数组与的乘积,结果与相同的,就将加,即跳过这个结果相同结果只存一次。 Problem Write a program to find the nth super ugly number. Super ugly numbers a...
摘要:滚动求最大值复杂度考虑一个,的值是下一个可能的替补值。思路数组中保存的是之前保留到的值,因为下一个可能的值是和之前的值的倍数关系。 Leetcode[313] Super Ugly Number Write a program to find the nth super ugly number. Super ugly numbers are positive numbers whos...
Problem Given two numbers n and k. We need to find out if n can be written as sum of k prime numbers. Example Given n = 10, k = 2Return true // 10 = 5 + 5 Given n = 2, k = 2Return false Solution pub...
阅读 769·2023-04-26 00:13
阅读 2633·2021-11-23 10:08
阅读 2374·2021-09-01 10:41
阅读 2075·2021-08-27 16:25
阅读 4103·2021-07-30 15:14
阅读 2313·2019-08-30 15:54
阅读 826·2019-08-29 16:22
阅读 2703·2019-08-26 12:13