Tìm hiểu xem hai số có tương đối chính

Question

Tôi đang cố gắng viết một phương pháp sẽ tính toán nếu hai số tương đối chính cho một bài tập. Tôi chủ yếu tìm kiếm câu trả lời về nơi bắt đầu. Tôi biết có một phương pháp gcd() mà sẽ làm rất nhiều cho tôi, nhưng việc chuyển nhượng là khá nhiều làm cho tôi làm điều đó mà không có gcd hoặc mảng.

Tôi đã bắt đầu, bởi vì tôi biết rằng tôi sẽ phải sử dụng toán tử % trong vòng lặp for.

public static boolean relativeNumber(int input4, int input5){ 
    for(int i = 1; i <= input4; i++) 

Rõ ràng phương pháp này được chỉ sẽ trở true hoặc false vì main hàm được chỉ sẽ in một dòng cụ thể tùy thuộc vào nếu hai con số nguyên tố cùng nhau hay không.

Tôi nghĩ tôi có thể sẽ phải viết hai for vòng, cả hai cho input4 và input5, và có thể một số loại if tuyên bố với một && toán hạng logic, nhưng tôi không chắc chắn.

Answer 1

Trong trường hợp chúng tương đối chính, bộ chia chung lớn nhất là một, bởi vì - nếu không - cả hai số có thể được chia cho số đó. Vì vậy, chúng ta chỉ cần một thuật toán để tính toán chia số chung lớn nhất, ví dụ Euclid's method:

private static int gcd(int a, int b) { 
    int t; 
    while(b != 0){ 
     t = a; 
     a = b; 
     b = t%b; 
    } 
    return a; 
} 

Và sau đó:

private static boolean relativelyPrime(int a, int b) { 
    return gcd(a,b) == 1; 
} 

thuật toán Euclid công trình trong O (log n) mà do đó là cách nhanh hơn liệt kê tất cả các ước số tiềm năng có thể được tối ưu hóa thành O (sqrt n).

Answer 2

package stack; 

import java.util.Scanner; //To read data from console 

/** 
* 
* @author base 
*/ 
public class Stack { 

    /** 
    * @param args the command line arguments 
    */ 
    public static void main(String[] args) { 
     Scanner in = new Scanner(System.in); // with Scanner we can read data 
     int a = in.nextInt(); //first variable 
     int b = in.nextInt(); //second variable 
     int max; // to store maximum value from a or b 
     //Let's find maximum value 
     if (a >= b) { 
      max = a; 
     } else { 
      max = b; 
     } 
     int count = 0; // We count divisible number 
     for (int i=2; i<=max; i++) { // we start from 2, because we can't divide on 0, and every number divisible on 1 
      if (a % i == 0 && b % i==0) { 
       count++; //count them 
      } 
     } 
     if (count == 0) { // if there is no divisible numbers 
      System.out.println("Prime"); // that's our solutions 
     } else { 
      System.out.println("Not Prime"); //otherwise 
     } 
    } 
} 

Tôi nghĩ rằng, đây là giải pháp đơn giản. Đặt câu hỏi trong nhận xét.

Answer 3

Swift 4 mã cho @ williem-van-onsem answer;

func gcd(a: Int, b: Int) -> Int { 
    var b = b 
    var a = a 
    var t: Int! 

    while(b != 0){ 
     t = a; 
     a = b; 
     b = t%b; 
    } 
    return a 
} 

func relativelyPrime(a : Int, b: Int) -> Bool{ 
    return gcd(a: a, b: b) == 1 
} 

Cách sử dụng;

print(relativelyPrime(a: 2, b: 4)) // false