服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|JAVA教程|ASP教程|

服务器之家 - 编程语言 - JAVA教程 - Java求素数和最大公约数的简单代码示例

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

2020-01-05 14:47捏造的信仰 JAVA教程

这篇文章主要介绍了Java求素数和最大公约数的简单代码示例,其中作者创建的Fraction类可以用来进行各种分数运算,需要的朋友可以参考下

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
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 对象时如果分母为零将会抛出异常,这也是必要的检查。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
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);
  }
}

 
运行输出:

?
1
2
3
4
{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)

延伸 · 阅读

精彩推荐