java编程实现求质数与因式分解代码分享

2024-03-28 12:41:11

1、求解质数

1.1说明

首先，我们来了解这样一个概念，那就是什么叫做质数？质数：一个数如果只能被1和它自己整除，这样的数被称为质数，与之对应的，称为和数。基于这样的一个概念，我们可以很快想到一个方法，就是从1开始，不断试探，看从1到它自己，是否有数字能够被他整除。

这样看来，其实求质数很简单，我们有没有更加便捷的方式呢？在这里介绍一个著名的Eratosthenes求质数方法。

1.2解法

首先知道这个问题可以使用回圈来求解，将一个指定的数除以所有小于它的数，若可以整除就不是质数，然而如何减少回圈的检查次数？如何求出小于N的所有质数？

假设要检查的数是N好了，则事实上只要检查至N的开根号就可以了，道理很简单，假设A*B=N，如果A大于N的开根号，则事实上在小于A之前的检查就可以先检查到B这个数可以整除N。不过在程式中使用开根号会精确度的问题，所以可以使用i*i<=N进行检查，且执行更快。

再来假设有一个筛子存放1～N，例如：

2　3　4　5　6　7　8　9　10　11　12　13　14　15　16　17　18　19　20　21 ........ N

先将2的倍数筛去：

2　3　5　7　9　11　13　15　17　19　21 ........ N

再将3的倍数筛去：

2　3　5　7　11　13　17　19　........ N

再来将5的倍数筛去，再来将7的质数筛去，再来将11的倍数筛去........，如此进行到最后留下的数就都是质数，这就是Eratosthenes筛选方法（EratosthenesSieveMethod）。

检查的次数还可以再减少，事实上，只要检查6n+1与6n+5就可以了，也就是直接跳过2与3的倍数，使得程式中的if的检查动作可以减少。

1.3代码

import java.util.*; 

public class Prime {
  public static int[] findPrimes(final int max) {
    int[] prime = new int[max+1];
    ArrayList list = new ArrayList(); 

    for(int i = 2; i <= max; i++)
      prime[i] = 1;  

    for(int i = 2; i*i <= max; i++) { // 这边可以改进
      if(prime[i] == 1) {
        for(int j = 2*i; j <= max; j++) {
          if(j % i == 0)
            prime[j] = 0;
        }
      }
    }  

    for(int i = 2; i < max; i++) {
      if(prime[i] == 1) {
        list.add(new Integer(i));
      }
    } 

    int[] p = new int[list.size()];
    Object[] objs = list.toArray();
    for(int i = 0; i < p.length; i++) {
      p[i] = ((Integer) objs[i]).intValue();
    } 

    return p;
  } 

  public static void main(String[] args) {
    int[] prime = Prime.findPrimes(1000); 

    for(int i = 0; i < prime.length; i++) {
      System.out.print(prime[i] + " ");
    } 

    System.out.println();
  }
}

2、因式分解

2.1说明

如上所示，我们先来了解一下，什么叫做因式分解？将一个数，转换成另外几个数字的乘积，就被称为因式分解。当了解到这样一个概念之后，我们对比上面的求解质数，应该能够明白，其实这里我们是在求解一个和数的因子。

因式分解基本上就是使用小于输入数的数值当作除数，去除以输入数值，如果可以整除就视为因数，要比较快的解法就是求出小于该数的所有质数，并试试看是不是可以整除。

2.2代码

import java.util.ArrayList; 

public class Factor {
  public static int[] factor(int num) {
    int[] pNum = Prime.findPrimes(num); 

    ArrayList list = new ArrayList(); 

    for(int i = 0; pNum[i] * pNum[i] <= num;) {
      if(num % pNum[i] == 0) {
        list.add(new Integer(pNum[i]));
        num /= pNum[i];
      }
      else
        i++;
    }  

    list.add(new Integer(num)); 

    int[] f = new int[list.size()];
    Object[] objs = list.toArray();
    for(int i = 0; i < f.length; i++) {
      f[i] = ((Integer) objs[i]).intValue();
    } 

    return f;
  } 

  public static void main(String[] args) {
    int[] f = Factor.factor(100);
    for(int i = 0; i < f.length; i++) {
      System.out.print(f[i] + " ");
    }
    System.out.println();
  }
}

3、总结

求解质数与因式分解，是学习程序与算法的基本功，应该熟练掌握，这里的代码只有少量的注释，可能对于初学者来说，略感吃力，但是这是进入程序算法殿堂的第一步。大家可以将这段代码拷贝到自己的机器上，逐步填上注释，让自己对程序流程更加清晰。

以上就是本文关于Java编程实现求质数与因式分解代码分享的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出！

Java模拟计算机的整数乘积计算功能示例

本文实例讲述了Java模拟计算机的整数乘积计算功能.分享给大家供大家参考,具体如下: 计算机计算整数乘积的原理: 实现代码: package math; public class two { /** * Fundamental method * f(n) = O(n^2) * @param a * @param b * @return */ public static int naiveMul(int a,int b){ int x = 0; //判断a中出现1的位置,每当出现1就将b的移位运算
浅谈Java中的高精度整数和高精度小数

在实际编码中,会遇到很多高精度的事例,比如,在计算金钱的时候就需要保留高精度小数,这样计算才不会有太大误差: 在下面的代码中,我们验证了,当两个float型的数字相加,得到的结果和我们的预期结果是有误差的,为了减小和防止这种误差的出现,我们需要使用BigInteger类和BigDecimal类来计算. package com.ietree.base.number; import java.math.BigDecimal; import java.math.BigInteger; public c
java中最大的整数用法分析

本文实例讲述了java中最大的整数用法.分享给大家供大家参考,具体如下: 8种基本数据类型中,long类型所能表示的整数范围是最大的,但还是有限的.另外,基本数据类型中的整数还有一个问题,那就是不是每个数都能够正确的取负数.例如,对int型而言,"-2147483648"取负就不能得到正确的结果,对其他整数类型也有这个问题. 为了解决这些问题,Java中专门提供了用来进行不限制大小的整数计算的类--java.math.BigInteger.该类可以对任意大小的整数进行操作,不过在进行计
Java统计50个10到50之间整数的随机出现次数

随机产生50个10到50的整数,统计每个数字各出现几次,出现0次的数字不打印. 代码如下: package com.homework.lhh; import java.util.Random; public class Ex04 { public static void main(String[] args) { int[] array = new int[50]; Random random = new Random(); for (int i = 0; i < array.length; i
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将一个正整数分解质因数的代码

程序分析:对n进行分解质因数,应先找到一个最小的质数k,然后按下述步骤完成: 1.如果这个质数恰等于n,则说明分解质因数的过程已经结束,打印出即可. 2.如果n <> k,但n能被k整除,则应打印出k的值,并用n除以k的商,作为新的正整数你,重复执行第一步. 3.如果n不能被k整除,则用k+1作为k的值,重复执行第一步. 程序设计: public class exp2{ public exp2(){} public void fengjie(int n){ for(int i=2;i<=
Java实现整数分解质因数的方法示例

本文实例讲述了Java实现整数分解质因数的方法.分享给大家供大家参考,具体如下: 题目内容: 每个非素数(合数)都可以写成几个素数(也可称为质数)相乘的形式,这几个素数就都叫做这个合数的质因数. 比如,6可以被分解为2x3,而24可以被分解为2x2x2x3. 现在,你的程序要读入一个[2,100000]范围内的整数,然后输出它的质因数分解式:当读到的就是素数时,输出它本身. 输入格式: 一个整数,范围在[2,100000]内. 输出格式: 形如: n=axbxcxd 或 n=n 所有的符号之间都
java求100之内的素数(质数)简单示例

质数又称素数.一个大于1的自然数,如果除了1和它自身外,不能被其他自然数整除的数:否则称为合数.根据算术基本定理,每一个比1大的整数,要么本身是一个质数,要么可以写成一系列质数的乘积:而且如果不考虑这些质数在乘积中的顺序,那么写出来的形式是唯一的.下面是一个java求100之内的素数简单示例复制代码代码如下: public class test { public static void main(String[] args) { int i,n,k=0; for (n = 3; n
java编程实现求质数与因式分解代码分享

1.求解质数 1.1说明首先,我们来了解这样一个概念,那就是什么叫做质数?质数:一个数如果只能被1和它自己整除,这样的数被称为质数,与之对应的,称为和数.基于这样的一个概念,我们可以很快想到一个方法,就是从1开始,不断试探,看从1到它自己,是否有数字能够被他整除. 这样看来,其实求质数很简单,我们有没有更加便捷的方式呢?在这里介绍一个著名的Eratosthenes求质数方法. 1.2解法首先知道这个问题可以使用回圈来求解,将一个指定的数除以所有小于它的数,若可以整除就不是质数,然而如何减少回
java编程基础之模仿用户登录代码分享

上一篇文章我们了解了Java背包问题求解实例代码,接下来我们看看Java中模仿用户登录的相关代码,下面是具体内容. 基于用户从控制台输入模拟的简陋用户登录验证Demo原理: 利用 Scanner 类中 nextLine() 提取用户从控制台输入的字符串信息利用 String 类的 equals 方法进行用户输入验证 import java.util.Scanner; public class Login { public static void main(String[] args) { //
java编程进行动态编译加载代码分享

简述该类使用javax.tools.ToolProvider自带的JavaCompiler进行编译,使用IO的File及NIO的Files进行对应的路径创建.读取及拷贝,使用正则表达式进行包名与目录的转换,我只是将这些东西做了个容错整合,没什么技术含量,就为个方便吧. 模块API class DynamicReactor://空参构造 public Class<?> dynamicCompile(String srcPath);//输入一个指定的源文件路径,若编译.拷贝成功则返回该类对应的C
Java编程接口调用的作用及代码分享

很多JAVA初级程序员对于接口存在的意义很疑惑.不知道接口到底是有什么作用,为什么要定义接口. 好像定义接口是提前做了个多余的工作.下面我给大家总结了4点关于JAVA中接口存在的意义: 1.重要性:在Java语言中, abstract class 和interface 是支持抽象类定义的两种机制.正是由于这两种机制的存在,才赋予了Java强大的面向对象能力. 2.简单.规范性:如果一个项目比较庞大,那么就需要一个能理清所有业务的架构师来定义一些主要的接口,这些接口不仅告诉开发人员你需要实现那些
Java编程实现深度优先遍历与连通分量代码示例

深度优先遍历深度优先遍历类似于一个人走迷宫: 如图所示,从起点开始选择一条边走到下一个顶点,没到一个顶点便标记此顶点已到达. 当来到一个标记过的顶点时回退到上一个顶点,再选择一条没有到达过的顶点. 当回退到的路口已没有可走的通道时继续回退. 而连通分量,看概念:无向图G的极大连通子图称为G的连通分量( Connected Component).任何连通图的连通分量只有一个,即是其自身,非连通的无向图有多个连通分量. 下面看看具体实例: package com.dataStructure.gra
Java编程将汉字转Unicode码代码示例

上一次接触到编码的知识,还是上大学的时候,那时候学的是通信工程专业,有关编码的内容,不记得是在通信原理还是信息论与编码里面学到的了.却依然记得那个信息论与编码的老师,最喜欢吃的是尖椒肥肠盖饭,不知道是尖椒肥肠吃多了还是太聪明的缘故,三十多岁就开始拜顶了.那四年真是一段难忘的回忆... 话不多说,咱们进入正题.这里是一个简单的Java编程将汉字转Unicode码代码示例,下面是代码: package me.socketthread; public class ToUnicode { /** * @
Java编程利用socket多线程访问服务器文件代码示例

这篇文章将向大家展示Java编程利用socket多线程访问服务器文件代码示例,如果您想先了解Java多线程socket编程的基础知识,可以看下这篇文章:Java多线程编程实现socket通信示例代码. 接下来进入正文,我们看看利用socket多线程访问服务器代码: ServerMain.java package com.ysk.webServer; import java.io.File; import java.io.IOException; import java.net.ServerSoc
Java编程GUI中的事件绑定代码示例

程序绑定的概念: 绑定指的是一个方法的调用与方法所在的类(方法主体)关联起来.对java来说,绑定分为静态绑定和动态绑定:或者叫做前期绑定和后期绑定静态绑定: 在程序执行前方法已经被绑定,此时由编译器或其它连接程序实现.例如:C. 针对java简单的可以理解为程序编译期的绑定:这里特别说明一点,java当中的方法只有final,static,private和构造方法是前期绑定动态绑定后期绑定:在运行时根据具体对象的类型进行绑定. 若一种语言实现了后期绑定,同时必须提供一些机制,可在运行期间
Java编程Post数据请求和接收代码详解

这两天在做http服务端请求操作,客户端post数据到服务端后,服务端通过request.getParameter()进行请求,无法读取到数据,搜索了一下发现是因为设置为text/plain模式才导致读取不到数据 urlConn.setRequestProperty("Content-Type","text/plain; charset=utf-8"); 若设置为以下方式,则通过request.getParameter()可以读取到数据 urlConn.setReq
Java编程实现邻接矩阵表示稠密图代码示例

我们知道,要表示结点,我们可以用一个一维数组来表示,然而对于结点和结点之间的关系,则无法简单地用一维数组来表示了,我们可以用二维数组来表示,也就是一个矩阵形式的表示方法. 我们假设A是这个二维数组,那么A中的一个元素aij不仅体现出了结点vi和结点vj的关系,而且aij的值正可以表示权值的大小. 邻接矩阵模型类邻接矩阵模型类的类名为AMWGraph.java,能够通过该类构造一个邻接矩阵表示的图,且提供插入结点,插入边,取得某一结点的第一个邻接结点和下一个邻接结点. import java.u

java编程实现求质数与因式分解代码分享

相关推荐

随机推荐