Java求素数和最大公约数的简单代码示例

Java小例子：求素数
素数（质数）指的是不能被分解的数，除了 1 和它本身之外就没有其它数能够整除。这里是一个小例子，说明如何求取十万以内的所有素数。
 
素数的分布没有规律可言，所以要检验一个数是不是素数，就必须将它同所有小于它的数作除法。不过有一个简便的方法，就是不需要检验所有小于它的数，而只要检验所有小于它的素数。如果所有小于它的素数都不能将其整除，那么它就是素数。

public class Primes { 

  public static void main(String[] args) {
    // 求素数
    List<Integer> primes = getPrimes(100000); 

    // 输出结果
    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;
  }
}

Java小例子：模拟分数的类 Fraction
这里是一个模拟分数运算的例子：Fraction 类。分数运算完后要用最大公约数除分子分母。所以这里也有个用辗转相除法求最大公约数的例子。另外在构造 Fraction 对象时如果分母为零将会抛出异常，这也是必要的检查。

public class FractionTest { 

  public static void main(String[] args) {
    Fraction a = new Fraction(7, 32);
    Fraction b = new Fraction(13, 32);
    System.out.println(a + " + " + b + " = " + a.add(b) + "(" + a.add(b).doubleValue() + ")");
    System.out.println(a + " - " + b + " = " + a.minus(b) + "(" + a.minus(b).doubleValue() + ")");
    System.out.println(a + " * " + b + " = " + a.multiply(b) + "(" + a.multiply(b).doubleValue() + ")");
    System.out.println(a + " / " + b + " = " + a.devide(b) + "(" + a.devide(b).doubleValue() + ")");
  }
} 

// 分数
class Fraction {
  private int numerator;   // 分子 

  private int denominator;  // 分母 

  Fraction(int numerator, int denominator) {
    if (denominator == 0) {
      throw new IllegalArgumentException("分母不能为 0");
    } 

    this.numerator = numerator;
    this.denominator = denominator;
    shrink();
  } 

  Fraction() {
    this(0, 1);
  } 

  public int getNumerator() {
    return numerator;
  } 

  public void setNumerator(int numerator) {
    this.numerator = numerator;
  } 

  public int getDenominator() {
    return denominator;
  } 

  public void setDenominator(int denominator) {
    this.denominator = denominator;
  } 

  // 分子分母同除以最大公约数
  private Fraction shrink() {
    int maxCommonDivisor = getMaxCommonDivisor(this.denominator, this.numerator);
    this.numerator /= maxCommonDivisor;
    this.denominator /= maxCommonDivisor;
    return this;
  } 

  // 辗转相除法求最大公约数
  private int getMaxCommonDivisor(int a, int b) {
    int mod = a % b; 

    if (mod == 0) {
      return b;
    } else {
      return getMaxCommonDivisor(b, mod);
    }
  } 

  // 分数加法
  public Fraction add(Fraction that) {
    return new Fraction(this.numerator * that.denominator + this.denominator * that.numerator,
        this.denominator * that.denominator);
  } 

  // 分数减法
  public Fraction minus(Fraction that) {
    return new Fraction(this.numerator * that.denominator - this.denominator * that.numerator,
        this.denominator * that.denominator);
  } 

  // 分数乘法
  public Fraction multiply(Fraction that) {
    return new Fraction(this.numerator * that.numerator,
        this.denominator * that.denominator);
  } 

  // 分数除法
  public Fraction devide(Fraction that) {
    return new Fraction(this.numerator * that.denominator,
        this.denominator * that.numerator);
  } 

  public double doubleValue() {
    return (double) numerator / denominator;
  } 

  @Override
  public String toString() {
    return String.format("{%d/%d}", this.numerator, this.denominator);
  }
}

运行输出：

{7/32} + {13/32} = {5/8}(0.625)
{7/32} - {13/32} = {-3/16}(-0.1875)
{7/32} * {13/32} = {91/1024}(0.0888671875)
{7/32} / {13/32} = {7/13}(0.5384615384615384)