Java实现求小于n的质数的3种方法
质数概念
质数，又称素数，指在一个大于1的自然数中，除了1和此整数自身外，无法被其他自然数整除的数（也可定义为只有1和本身两个因数的数）。
最小的素数是2，也是素数中唯一的偶数；其他素数都是奇数。质数有无限多个，所以不存在最大的质数。
一：根据定义去求解：
也是最笨的方式，效率比较低：
package test.ms;
public class FindPrime {
// 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：平方根：
package test.ms;
public class Prime {
public static void main(String[] args) {
for(int j = 2; j<1000; j++){
if(m(j)){
System.out.print(j+" ");
}
}
}
public static boolean m(int num){
for(int j = 2; j<=Math.sqrt(num);j++){
if(num%j == 0){
return false;
}
}
return true;
}
}
3：找规律（摘自一个论坛讨论）
最小的素数是2，也是素数中唯一的偶数；其他素数都是奇数。质数有无限多个，所以不存在最大的质数。
package test.ms;
import java.util.ArrayList;
import java.util.List;
public class Primes {
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数学归纳法非递归求斐波那契数列的方法
本文实例讲述了java数学归纳法非递归求斐波那契数列的方法.分享给大家供大家参考.具体如下: Integer能表示的最大值为 2147483647 大概是21.4亿,这里没有考虑溢出情况(当size为983时就会溢出)! import java.util.List; import java.util.ArrayList; /** * @author jxqlovejava * 斐波那契数列 */ public class Fibonacci { public static List<Intege
-
使用Java代码进行因数分解和求最小公倍数的示例
因数分解 /* 因数分解是十分基本的数学运算,应用广泛.下面的程序对整数n(n>1)进行因数分解. 比如,n=60, 则输出:2 2 3 5.请补充缺失的部分. */ public class 因数分解 { public static void f(int n) { for (int i = 2; i < n / 2; i++) { while(n%i==0){ // 填空 System.out.printf("%d ", i); n = n / i; } } if (n
-
Java求素数和最大公约数的简单代码示例
Java小例子:求素数 素数(质数)指的是不能被分解的数,除了 1 和它本身之外就没有其它数能够整除.这里是一个小例子,说明如何求取十万以内的所有素数. 素数的分布没有规律可言,所以要检验一个数是不是素数,就必须将它同所有小于它的数作除法.不过有一个简便的方法,就是不需要检验所有小于它的数,而只要检验所有小于它的素数.如果所有小于它的素数都不能将其整除,那么它就是素数. public class Primes { public static void main(String[] args)
-
java求最大公约数与最小公倍数的方法示例
本文实例讲述了java求最大公约数与最小公倍数的方法.分享给大家供大家参考,具体如下: Gongyueshu.java文件: package math; public class Gongyueshu { public static void main(String[] args) { //从控制台输入两个数据 int m = Integer.parseInt(args[0]); int n = Integer.parseInt(args[1]); int y = 1 ; int b = 1;
-
Java求字符串中出现次数最多的字符串以及出现次数
金山公司面试题:一个字符串中可能包含a~z中的多个字符,如有重复,如String data="aavzcadfdsfsdhshgWasdfasdf",求出现次数最多的那个字母及次数,如有多个重复的则都求出. 此题的解题思路如下: 引入TreeSet:通过集合快速找到所有出现过的字符串 引入ArrayList:为了快速排序,再通过StringBuffer生成排序后的字符串 通过String的indexOf方法和lastIndexOf方法来计算每个字符串出现的次数最大值 使用HashMap
-
java 求解二维数组列最小值
java 求解二维数组列最小值 比较二维数组列最小值,组成一个新数组返回. 实现核心算法,不需要使用IO 输入:{{5,6,1,16},{7,3,9}} 输出:{1,3} import java.util.Arrays; public class Col { public static int[] getColMin(int a[][]) { int[] res = new int[a.length]; for (int i = 0; i < a.length; i++) { int[] s =
-
Java中使用辗转相除法求最大公约数
比较好用的是辗转相除法. 比如:49和91 a b temp 49 % 91 = 49 91 % 49 = 42 49 % 42 = 7 42 % 7 = 0 所以最大公约数就是7. public class T { public static void main(String[] args) { int gcd = gcd(91, 49); System.out.println(gcd); } /** * greatest comm
-
Java求两个正整数的最大公约数和最小公倍数
题目:输入两个正整数m和n,求其最大公约数和最小公倍数. 程序分析:利用辗除法. 最大公约数: public class CommonDivisor{ public static void main(String args[]) { commonDivisor(24,32); } static int commonDivisor(int M, int N) { if(N<0||M<0) { System.out.println("ERROR!"); return -1; }
-
java求两个数中的大数(实例讲解)
java中的max函数在Math中 应用如下: int a=34: int b=45: int ans=Math.max(34,45); 那么ans的值就是45. 以上这篇java求两个数中的大数(实例讲解)就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们.
-
Java实现求小于n的质数的3种方法
质数概念 质数,又称素数,指在一个大于1的自然数中,除了1和此整数自身外,无法被其他自然数整除的数(也可定义为只有1和本身两个因数的数). 最小的素数是2,也是素数中唯一的偶数:其他素数都是奇数.质数有无限多个,所以不存在最大的质数. 一:根据定义去求解: 也是最笨的方式,效率比较低: package test.ms; public class FindPrime { // find the prime between 1 to 1000; public static void main(Str
-
java 在file的尾部添加数据的两种方法总结
java 在file的尾部添加数据的两种方法总结 问题描述: 在文件的末尾追加内容 方法1:利用RandomAccessFile类 1.将randomAccessFile模式设置为rw 2将randomAccessFile移动(seek)到文件末尾 3追加数据 4关闭流 方法2:利用FileWriter类 1.将FileWriter构造方法第二个参数置为true.表示在尾部追加 2追加数据 3.关闭流 实现代码: package cn.com; import java.io.F
-
Java Swing实现窗体添加背景图片的2种方法详解
本文实例讲述了Java Swing实现窗体添加背景图片的2种方法.分享给大家供大家参考,具体如下: 在美化程序时,常常需要在窗体上添加背景图片.通过搜索和测试,发现了2种有效方式.下面分别介绍. 1. 利用JLabel加载图片 利用JLabel自带的setIcon(Icon icon)加载icon,并设置JLabel对象的位置和大小使其完全覆盖窗体.这是一个很取巧的办法,代码非常简单,如下所示. JLabel lbBg = new JLabel(imageIcon); lbBg.setBound
-
Java实现对象按照其属性排序的两种方法示例
本文实例讲述了Java实现对象按照其属性排序的两种方法.分享给大家供大家参考,具体如下: 有时候需要对对象列表或数组进行排序,下面提供两种简单方式: 方法一:将要排序的对象类实现Comparable<>接口. 首先,创建学生类,我们将根据学生成绩对学生进行排序: /** * 学生类 */ class Student implements Comparable<Student>{ String name; int age; int score; public Student(Stri
-
详解Java Web如何限制访问的IP的两种方法
前一阵子因为在做项目时碰到了这个功能,现在好好总结一下,至于为什么要限制IP访问,我就不多说了.然后百度了一下,现在主要有两种方式去限制IP访问,第一种是最简单的方便的,第二种是通过过滤器来限制访问.下面我简单介绍一下第一种方式,着重介绍第二种. 第一种方式(Tomcat配置项配置允许或限制IP访问) 这种是最简单的快捷的,主要就涉及Tomcat的server.xml配置. 第一步:找到server.xml文件在哪,在Tomcat的目录下的conf文件夹下. 第二步:打开server.xml文件
-
浅谈Java中Collections.sort对List排序的两种方法
目录 一.Collections.sort的简单使用 二.问题提出 三.Comparable实现排序 四.Comparator实现排序 五.Comparable 与Comparator区别 一.Collections.sort的简单使用 说到List的排序,第一反应当然是使用Collections.sort,方便简单.下面实现一下~~ private void sortStrings() { List<String> list = new ArrayList<String>();
-
Java如何设置过期时间的map的几种方法
目录 一.技术背景 二.技术效果 三.ExpiringMap 3.1功能简介 3.2源码 3.3示例 四.LoadingCache 4.1功能简介 4.2示例 4.3移除机制 4.4其他 五.HashMap的封装 一.技术背景 在实际的项目开发中,我们经常会使用到缓存中间件(如redis.MemCache等)来帮助我们提高系统的可用性和健壮性. 但是很多时候如果项目比较简单,就没有必要为了使用缓存而专门引入Redis等等中间件来加重系统的复杂性.那么Java本身有没有好用的轻量级的缓存组件呢.
-
python求质数的3种方法
本文为大家分享了多种方法求质数python实现代码,供大家参考,具体内容如下 题目要求是求所有小于n的质数的个数. 求质数方法1: 穷举法: 根据定义循环判断该数除以比他小的每个自然数(大于1),如果有能被他整除的就不是质数: def countPrimes1(self, n): """ :type n: int :rtype: int """ if n<=2: return 0 else: res=[] for i in range(2,
-
java发送url请求获取返回值的二种方法
下面提供二种方法会使用java发送url请求,并获取服务器返回的值 第一种方法: 复制代码 代码如下: import org.apache.http.HttpEntity;import org.apache.http.HttpResponse;import org.apache.http.NameValuePair;import org.apache.http.client.HttpClient;import org.apache.http.client.entity.UrlEncodedFor
-
Java中启动线程start和run的两种方法
一.区别 Java中启动线程有两种方法,继承Thread类和实现Runnable接口,由于Java无法实现多重继承,所以一般通过实现Runnable接口来创建线程.但是无论哪种方法都可以通过start()和run()方法来启动线程,下面就来介绍一下他们的区别. start方法: 通过该方法启动线程的同时也创建了一个线程,真正实现了多线程.无需等待run()方法中的代码执行完毕,就可以接着执行下面的代码.此时start()的这个线程处于就绪状态,当得到CPU的时间片后就会执行其中的run()方法.