Answer to Question #100114 in Java | JSP | JSF for Sam Wilson

Question

Write a Java program to create a two-dimension array (m x m) A[][] such that A[i][j] is true if i and j are prime and have no common factors, otherwise A[i][j] becomes false.

Answer 1

Since I have not received answers to my questions in time, I decided to make two versions of code. 

The first one sets true only when both i and j are prime (therefore they do not have common factors), cases when i == j set as false (they have each other as composite number). 

The second one sets true when both i and j are prime OR i and j have no common numbers. Cases when i == j set as false in this version too.

Please choose the version which is better for you.

1)

import java.util.Scanner;

public class MainClass {

	public static void main(String[] args) {
		int m = GetArrayDimension();
		boolean[][] A = new boolean[m][m];
		//all elements with indexes 0 or 1 left by default (false), because this numbers considered not prime nor composite
		
		int[] primeNumbers = findAllPrime(m - 1);		
		
		for(int i : primeNumbers) {
			for (int j : primeNumbers) {
				if (i != j)
					A[i][j] = true;
			}
		}
		System.out.println("Your array: ");
		printArray(A, m);
	}
	
	static int GetArrayDimension() {
		System.out.println("Enter value m for the array m x m:");
		Scanner scan = new Scanner(System.in);
		int m = 0;
		do {
			if(scan.hasNextInt())
				m = scan.nextInt();
			else 
				scan.nextLine();
		} while (m <= 0);
		scan.close();
		return m;
	}
	
	static int[] findAllPrime(int n) { //used Sieve of Eratosthenes algorithm
		int arraySize = n - 1;
    int[] all = new int[arraySize];
    int curNum = 2;
    for (int i = 0; i <= arraySize - 1; i++)
    {
      all[i] = curNum++;
    }
    int countPrimes = n - 1;
    int p = all[0]; //p is a step of algorithm
    while (p <= n)
    {
    	//mark found composite numbers as 0
      for (int i = 2*p - 2; i < arraySize; i = i + p)
      {
      	if (all[i] != 0)
          countPrimes--;
        all[i] = 0;
      }
      //find new step
      int oldP = p;
      for (int i = p - 1; i < arraySize; i++)
      {
        if (all[i] != 0)
        {
          p = all[i];
          break;
        }
      }
      if (p == oldP)
        break;
    }
    //rewrite into array only prime numbers
    int[] primes = new int[countPrimes];
    for (int i = 0, j = 0; i < arraySize; i++) {
    	if (all[i] != 0) {
    		primes[j] = all[i];
    		j++;
    	}
    }
    return primes;
	}
	
	static void printArray(boolean[][] A, int size) {
		System.out.print("\t");
		for (int i = 0; i < size; i++) {
			System.out.print(i + "\t");
		}
		System.out.println();
		for (int i = 0; i < size; i++) {
			for(int j = -1; j < size; j++) {
				if (j == -1)
					System.out.print(i + "\t");
				else
					System.out.print(A[i][j] + "\t");
			}
			System.out.println();
		}
	}
}

2)

import java.util.Scanner;

public class MainClass {

	public static void main(String[] args) {
		int m = GetArrayDimension();
		boolean[][] A = new boolean[m][m];

		int[] primeNumbers = findAllPrime(m - 1);
		//all elements with indexes 0 or 1 left by default (false), because these numbers considered not prime nor composite
		for(int i = 2; i < m; i++) {
			boolean isPrimeI = isInArray(primeNumbers, i);
			for (int j = 2; j < m; j++) {
				if (i != j) { //if i and j equal then they have a common number - it is i (or j) itself
					if (isPrimeI && isInArray(primeNumbers, j)) {
						A[i][j] = true;
					}
					else {
						if (i < j) {
							if(!hasCommonFactors(i, j)) 
								A[i][j] = true;
						}
						else {
							A[i][j] = A[j][i]; //we have already looked for common factors for i and j
						}
					}
				}
			}
		}
		
		System.out.println("Your array: ");
		printArray(A, m);
	}
	
	static int GetArrayDimension() {
		System.out.println("Enter value m for the array m x m:");
		Scanner scan = new Scanner(System.in);
		int m = 0;
		do {
			if(scan.hasNextInt())
				m = scan.nextInt();
			else 
				scan.nextLine();
		} while (m <= 0);
		scan.close();
		return m;
	}
	
	static boolean hasCommonFactors(int a, int b) { //used Euclidean algorithm
		if (a == b)
			return true;
		if (a < b) { //replace
			int temp = a;
			a = b;
			b = temp;
		}
		int mod = 0;
		int prevMod;
		do {
			prevMod = mod;
			mod = a % b;
			a = b;
			b = mod;
		} while(mod != 0);
		if (prevMod == 1)
			return false;
		else
			return true;
	}
	
	static int[] findAllPrime(int n) { //used Sieve of Eratosthenes algorithm
		int arraySize = n - 1;
    int[] all = new int[arraySize];
    int curNum = 2;
    for (int i = 0; i <= arraySize - 1; i++)
    {
      all[i] = curNum++;
    }
    int countPrimes = n - 1;
    int p = all[0]; //p is a step of algorithm
    while (p <= n)
    {
    	//mark found composite numbers as 0
      for (int i = 2*p - 2; i < arraySize; i = i + p)
      {
      	if (all[i] != 0)
          countPrimes--;
        all[i] = 0;
      }
      //find new step
      int oldP = p;
      for (int i = p - 1; i < arraySize; i++)
      {
        if (all[i] != 0)
        {
          p = all[i];
          break;
        }
      }
      if (p == oldP)
        break;
    }
    //rewrite into array only prime numbers
    int[] primes = new int[countPrimes];
    for (int i = 0, j = 0; i < arraySize; i++) {
    	if (all[i] != 0) {
    		primes[j] = all[i];
    		j++;
    	}
    }
    return primes;
	}
	
	static boolean isInArray(int[] array, int number) {
		for (int i = 0; array[i] <= number; i++) {
			if (array[i] == number)
				return true;
			if(i + 1 == array.length)
				return false;
		}
		return false;
	}
	
	static void printArray(boolean[][] A, int size) {
		System.out.print("\t");
		for (int i = 0; i < size; i++) {
			System.out.print(i + "\t");
		}
		System.out.println();
		for (int i = 0; i < size; i++) {
			for(int j = -1; j < size; j++) {
				if (j == -1)
					System.out.print(i + "\t");
				else
					System.out.print(A[i][j] + "\t");
			}
			System.out.println();
		}
	}
}