首页 > 代码库 > Java质数求解
Java质数求解
质数概念
质数,又称素数,指在一个大于1的自然数中,除了1和此整数自身外,无法被其他自然数整除的数(也可定义为只有1和本身两个因数的数)。最小的素数是2,也是素数中唯一的偶数;其他素数都是奇数。质数有无限多个,所以不存在最大的质数。
目前总结大概有3中计算方式求解,具体如下
1. 粗鲁暴力定义求解法
public class Prime { // find the prime between 1 to 1000; public static void main(String[] args) { printPrime(1000); } public static void printPrime(int n) { for (int i = 2; i < n; i++) { int count = 0; for (int j = 2; j <= i; j++) { if (i % j == 0) { count++; } if (j == i && count == 1) { System.out.print(i + " "); } if (count > 1) { break; } } } } }
2. 平方根算法(降低循环次数)
public class Prime { // find the prime between 1 to 1000; public static void main(String[] args) { for (int i = 2; i < 1000; i++) { if (isPrime(i)) { System.out.print(i + " "); } } } /** * 求指定数是否为质数 * @param num * @return */ public static boolean isPrime(int num) { for (int j = 2; j <= Math.sqrt(num); j++) { if (num % j == 0) { return false; } } return true; } }
3. 规律法
最小的素数是2,也是素数中唯一的偶数;其他素数都是奇数。质数有无限多个,所以不存在最大的质数。
public class Prime { // find the prime between 1 to 1000; public static void main(String[] args) { List<Integer> primes = getPrimes(1000); // 输出结果 for (int i = 0; i < primes.size(); i++) { Integer prime = primes.get(i); System.out.printf("%8d", prime); if (i % 10 == 9) { System.out.println(); } } } /** * 求 n 以内的所有素数 * @param n 范围 * @return n 以内的所有素数 */ private static List<Integer> getPrimes(int n) { List<Integer> result = new ArrayList<Integer>(); result.add(2); for (int i = 3; i <= n; i += 2) { if (!divisible(i, result)) { result.add(i); } } return result; } /** * 判断 n 是否能被整除 * @param n 要判断的数字 * @param primes 包含素数的列表 * @return 如果n能被 primes中任何一个整除,则返回 true。 */ private static boolean divisible(int n, List<Integer> primes) { for (Integer prime : primes) { if (n % prime == 0) { return true; } } return false; } }
第一种和第二种都是很简单的方法:
第三种方法说明了一个质数的特性:在所有质数中,只有2是偶数。如果一个数能够被它之前的质数整除,那么这个数不是质数。
Java质数求解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。