Нахождение ГКД путем разложения на простые факторы - PullRequest
Новая
       37

Нахождение ГКД путем разложения на простые факторы

0 голосов
/ 18 декабря 2018

Я должен написать программу, которая вычисляет GCD, находя взаимные простые факторы в двух числах.Программа выведет два списка простых множителей двух заданных чисел и в последней строке напишет список с взаимными числами. 

public static void main(String[] args) {
      Scanner in=new Scanner(System.in);
      ArrayList <Integer> LIST1=new ArrayList<Integer>();
      ArrayList <Integer> LIST2=new ArrayList <Integer>();
      ArrayList <Integer> LIST3=new ArrayList <Integer>();
      int a=in.nextInt();
      int b=in.nextInt();
      int i;
      for(i=2;i<=a;i++){
         while(a%i==0){           LIST1.add(i);  
            a=a/i;}
      }
      int j;
      for(j=2;j<=b;j++){
         while(b%j==0){
            LIST2.add(j);
            b=b/j;
         }
      }
     int p = LIST1.size();
     int q = LIST2.size();
     int MIN=Math.min(p,q);
      int k;
      for(k=0;k<=MIN-1;k++){
         int m;
         for(m=0;m<=MIN-1;m++){
            if(LIST1.get(k)==LIST2.get(m)){
                 int c=LIST1.get(k);
                 LIST3.add(c); 
            } 
         } 
      }
      System.out.println(LIST1);
      System.out.println(LIST2);
      System.out.println(LIST3);
    }

1 Ответ

0 голосов
/ 18 декабря 2018

Нахождение основных факторов a и b мне кажется правильным.

Но логика в поиске общих факторов, вероятно, неверна.Попробуйте, например, с 24 и 40, и пошагово пройдитесь по части коллекции LIST3.Как часто вы собираете фактор 2 в результат?Поскольку GCD равен 8, вы должны рассчитывать фактор 2 ровно три раза.Может быть сложно найти общее подмножество двух списков, в которых элементы могут встречаться более одного раза.

Может быть проще собрать простые факторы не в List, но в Map с помощьюглавный фактор как ключ и число как значение.Если вы раньше не использовали Map, то абсолютно стоит узнать об этой структуре данных.

PS, когда вы правильно запустили программу, я бы рекомендовал опубликовать ее на https://codereview.stackexchange.com/ где мы можем дать вам несколько полезных советов по стилю кодирования, которые не подходят для Stackoverflow.

...