Ex_1_1_30.md

title	date	draft	tags	categories
算法4 Java解答 1.1.30	2019-03-02 19:38:48 +0800	false	JAVA	技术 归档

1.1.30

问题：

Array exercise. Write a code fragment that creates an N-by-N boolean array a[][] such that a[\i][\j] is true if i and j are relatively prime (have no common factors), and false otherwise.

分析：

In number theory, two integers a and b are said to be relatively prime, mutually prime,or coprime (also written co-prime) if the only positive integer (factor) that divides both of them is 1.

SOLUTION:

step 1: generate a N-N boolean array

step 2: for index i,j check if the corresponding gcd is equal to 1. if gcd(i,j) is 1 then set a[i][[j]=true

  public static boolean[][] genArray(int N){
    boolean[][] a = new boolean[N][N];
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        if(gcd(i,j)==1){
          a[i][j] = true;
        }
      }
    }
    return a;
  }

参考：

coprime