Нахождение факторов заданного целого числа - PullRequest
Новая
       33

Нахождение факторов заданного целого числа

6 голосов
/ 27 декабря 2011

У меня что-то вроде этого: 

int f = 120;
for(int ff = 1; ff <= f; ff++){
    while (f % ff != 0){            
}

Что-то не так с моим циклом для поиска факторов?Я действительно запутался в том, как работают операторы for и while, поэтому есть вероятность, что они совершенно неверны.

После этого, как бы мне было назначить переменные для указанных факторов?

Ответы [ 14 ]

10 голосов
/ 22 февраля 2016 
public class Solution {
    public ArrayList<Integer> allFactors(int a) {

        int upperlimit = (int)(Math.sqrt(a));
        ArrayList<Integer> factors = new ArrayList<Integer>();
        for(int i=1;i <= upperlimit; i+= 1){
            if(a%i == 0){
                factors.add(i);
                if(i != a/i){
                    factors.add(a/i);
                }
            }
        }
        Collections.sort(factors);
        return factors;
    }
}

Приведенное выше решение просто работает как вычисление простых факторов.Разница заключается в том, что для каждого простого фактора мы продолжаем вычислять другую часть продукта, то есть число reqd.

9 голосов
/ 02 декабря 2015

Вот как получить все множители заданного числа. 

public class Factors {

    public static void main(String[] args){
        int n = 420;

        for(int i=2; i<=n; i++){
            while(n%i==0){
                System.out.println(i + "| " + n);
                System.out.println(" -----");
                n = n/i;
            }
        }
    }
}

Вывод: 

2| 420
 -----
2| 210
 -----
3| 105
 -----
5| 35
 -----
7| 7
 -----
7 голосов
/ 21 августа 2017

Следующий код вернет список всех факторов данного числа: 

public ArrayList<Integer> findFactors(int num) {        
    ArrayList<Integer> factors = new ArrayList<Integer>();

    // Skip two if the number is odd
    int incrementer = num % 2 == 0 ? 1 : 2;

    for (int i = 1; i <= Math.sqrt(num); i += incrementer) {

        // If there is no remainder, then the number is a factor.
        if (num % i == 0) {
            factors.add(i);

            // Skip duplicates
            if (i != num / i) {
                factors.add(num / i);
            }

        }
    }

    // Sort the list of factors
    Collections.sort(factors);

    return factors;
}

Этот ответ улучшает Ответ Шарад Даргана двумя способами:

  1. Основываясь на идее, использованной в в этом ответе , вы можете ускорить решение, определив значение для приращения на основе четного или нечетного числа.

    Добавьте следующую строку кода перед циклом for: 

    int incrementer = num % 2 == 0 ? 1 : 2;

    Затем измените последнюю часть цикла на: 

     i += incrementer

    Если число нечетное, оно будет пропускать все четные числа, а не всегда увеличиваться на единицу независимо от того, что.

  2. Sharad сохраняет значение верхнего предела в переменной, а затем использует эту переменную в цикле for: 

    int upperlimit = (int)(Math.sqrt(a));
...
for(int i = 1; i <= upperlimit; i+= 1)

    Вместо этого поместите Math.sqrt(num) непосредственно в цикл for и пропустите верхнюю граничную переменную: 

    for (int i = 1; i <= Math.sqrt(num); i += incrementer) {

    Это позволит вам пропустить часть кода, создающую более чистый код.

Некоторые тестовые случаи JUnit, которые вы можете использовать: 

@Test
public void test12() {
    FindFactors find = new FindFactors();

    int num = 12;
    List<Integer> factors = Arrays.asList(1, 2, 3, 4, 6, 12);

    assertEquals(factors, find.findFactors(num));
}

@Test
public void test1000000() {
    FindFactors find = new FindFactors();

    int num = 1000000;
    List<Integer> factors = Arrays.asList(1, 2, 4, 5, 8, 10, 16, 20, 25, 32, 40, 50, 64, 80, 100, 125, 160, 200,
            250, 320, 400, 500, 625, 800, 1000, 1250, 1600, 2000, 2500, 3125, 4000, 5000, 6250, 8000, 10000, 12500,
            15625, 20000, 25000, 31250, 40000, 50000, 62500, 100000, 125000, 200000, 250000, 500000, 1000000);

    assertEquals(factors, find.findFactors(num));
}

@Test
public void test1() {
    FindFactors find = new FindFactors();

    int num = 1;
    List<Integer> factors = Arrays.asList(1);

    assertEquals(factors, find.findFactors(num));
}

@Test
public void test0() {
    FindFactors find = new FindFactors();

    int num = 0;
    List<Integer> factors = new ArrayList<Integer>();

    assertEquals(factors, find.findFactors(num));
}
3 голосов
/ 10 марта 2017

Чтобы найти факторы для данного числа, вам нужно только проверить квадратный корень из данного числа.

Например, чтобы найти факторы 6, вам нужно проверить только до 2,45 (√6). Коэффициенты 6 будут равны 1 и 2, и их обратные числа, то есть 3 и 6.

Я создал программу, которая определяет факторы заданного числа и отображает их. Вот необходимый код: 

    Scanner input = new Scanner(System.in);

    System.out.print("Enter integer: ");
    long num = input.nextLong();

    for(long i = 1; i <= Math.sqrt(num); i++) {
        if(num % i == 0) {
            System.out.println(i);
            if(i != num/i) {
                System.out.println(num/i);
            }
        }
    }

Вам просто нужна эта программа, чтобы найти факторы заданного числа. Однако, если вы хотите сделать еще один шаг и отобразить факторы , расположенные в порядке возрастания , то необходимый код будет следующим: 

    Scanner input = new Scanner(System.in);

    System.out.print("Enter integer: ");
    long num = input.nextLong();

    ArrayList<Long> list1 = new ArrayList<>(), list2 = new ArrayList<>();

    long currentTime = System.currentTimeMillis();

    for(long i = 1; i <= Math.sqrt(num); i++) {
        if(num % i == 0) {
            list1.add(i);
            if(i != num/i) {
                list2.add(num/i);
            }
        }
    }

    int n1 = list1.size() - 1;
    int n2 = list2.size() - 1;

    for(int i = 0; i <= n1; i++) {
        System.out.println(list1.get(i));
    }

    for(int i = n2; i >= 0; i--) {
        System.out.println(list2.get(i));
    }

Что это делает: Эта программа сохраняет множители числа до квадратного корня числа в одном списке (list1) и обратное преобразование этих чисел в другом списке (list2). Затем он печатает элементы обоих списков (как показано).

2 голосов
/ 28 декабря 2011

Нет ничего плохого в вашем цикле for, но цикл while не подходит для использования здесь.Логика вашей петли for:

  • Установите ff на 1.
  • Продолжайте, пока ff <= f.
  • После того, как вы сделаливсе в цикле for, добавьте 1 к ff.

Это выглядит так, как вы хотите.

Цикл while не верен,хоть.Он будет продолжать делать любой код, который вы там пишете, пока ff имеет коэффициент f, поэтому, если вы не измените их в коде while, вы получите бесконечный цикл.Однако, изменив это выражение на if, вы получите то, что вы хотите.

Поскольку вы проверяете факторы, вам не нужно проверять все возможности вплоть до f - только до квадрата.корень ф.Всякий раз, когда вы обнаружите, что ff является фактором, выведите как ff и f/ff как факторы, если только f не является квадратным числом.

0 голосов
/ 04 июля 2019 
public static void printFactors(int number) {
    if (number < 1 )
        System.out.println("Invalid Value");

    for (int i = 1 ; i <= number ; ++i) {
        if ( number % i == 0)
                System.out.println(i);
        }
    }
}
0 голосов
/ 11 октября 2018

Вот так ты сам пишешь, как босс.Необходимо добавить операторы if для обработки одного и двух, но помимо этого;этот метод так же сексуален, как и получает 

  public static void primerize(int n){
  boolean reduced = false;
  while(n > 2){
     if(n%2 == 0){
        System.out.println(2 + "," + n/2);
        n /= 2;
     }
     else{
        int i = isPrime(n); 
        if(i == n && reduced == false){
           System.out.println(1 + "," + n);
           n /= n;
        }
        else if(i == n){
           n/= n;
        }
        else{
           System.out.println(i + "," + n/i);
           n = i;
           reduced = true;
        }
     }
  }}



public static int isPrime(int n){
  for(int i = (n/3); i > 0; i--){
     if(i == 1){
        return n;
     }
     else if(n%i == 0){
        return i;
     }
  }
  return 0;}
0 голосов
/ 03 августа 2018

Используя потоки, представленные в Java 8, ниже будут напечатаны коэффициенты для данного числа. 

int input = 1500;
IntStream.rangeClosed(1, input)
         .filter(e -> input % e == 0)
         .forEach(System.out::println);
0 голосов
/ 03 июля 2018 
    import java.util.Scanner;
    public class Factors 
    {
        Scanner scn=new Scanner(System.in);
        int num=scn.nextInt();
        public void findFactor()
        {
           System.out.println("Factors are");
           System.out.println("1");
           for(int i=2;i<=num;i++)
           {
                if(num%i==0)
                {
                    num=num/i;
                    System.out.println(i);
                    i=2;
                }
           }
        }
public static void main(String[] args) 
{
    while(1==1)
    {
        System.out.println("Enter a Number");
        Factors fct=new Factors();
        fct.findFactor();
    }
}

}

0 голосов
/ 30 апреля 2016

Самый простой способ с использованием рекурсивной функции 

public static int factorial(int n){
        if(n!=1)
            return n*factorial(n-1);
        return 1; 
}
Страница:
...