Наибольшее число палиндром, которое является произведением двух простых пятизначных чисел

#android #циклы #простые_числа

Делал приложение по ТЗ из одной компании. Сделал андроид-аппку, получил результат
на эмуляторе, вроде же верный. Но HR просто отписалась, что ответ который выдало мое
приложение неверен.
Айчары люди довольно занятые, потому редко кто может указать на ошибку, а навязываться
после отказа - дело очень неблагодарное. Но все же хочется хоть для себя выполнить
задание до конца.

Из требований было:


  Напишите программу, которая возвращает наибольшее число палиндром, которое
  является произведением двух простых пятизначных чисел, а также возвращает
  сами сомножители.
  Простое число - это натуральное число, которое делится нацело только на 1 и
  на себя само (2, 3, 5, 7, 11, …)
  Палиндром – строка, которая читается одинаково в обоих направлениях
  (например ABBA)


Сам принцип поиска простых чисел мне понятен. Использовать массивы было нецелесообразно
потому  решето Эратосфена и аналоги пришлось отбросить - уж очень много памяти сожрало
бы создание массива на такое количество значений.

Потому решил использовать циклы для сопоставления и отсеивания.

Вот код моего андроид-приложения:

MainActivity:

public class MainActivity extends AppCompatActivity implements View.OnClickListener {

    private int maxNum = 99999;
    private int minNum = 10000;

    private int divNumMax = 0;
    private int palind;

    private TextView tv1;
    private TextView tv2;
    private TextView tv3;
    private TextView tv4;


    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);

        tv1 = (TextView) findViewById(R.id.textView1);
        tv2 = (TextView) findViewById(R.id.textView2);
        tv3 = (TextView) findViewById(R.id.textView3);
        tv4 = (TextView) findViewById(R.id.textView4);

        Button btnStart = (Button) findViewById(R.id.button);
        btnStart.setOnClickListener(this);

    }

    @Override
    public void onClick(View v) {

        divNumMax = (int) Math.sqrt(maxNum);

        int fPM;
        int sPM;
        boolean isNotPalind;

        fPM = findMaxPrimeNumber(maxNum);
        sPM = findMaxPrimeNumber(fPM - 2);
        isNotPalind = findPalindrome(fPM, sPM);

        while (isNotPalind) {

            if (sPM <= fPM && sPM > minNum) {
                sPM = findMaxPrimeNumber(sPM - 2);
                isNotPalind = findPalindrome(fPM, sPM);

            } else if (sPM <= minNum) {
                fPM = findMaxPrimeNumber(fPM - 2);
                sPM = fPM;
            }

            tv2.setText("1-st primary number: " + fPM);
            tv3.setText("2-nd primary number: " + sPM);
            tv4.setText("1-st * 2-nd = " + palind);

        }
    }


    private int findMaxPrimeNumber(int maxNumPre) {
        int i;
        int j;
        int z;
        int maxNumNew;

        for (i = maxNumPre; i >= minNum; i = i - 2) {

            for (j = 3; j <= divNumMax; j++) {

                z = i % j;

                if (z == 0 && j <= divNumMax) {
                    break;

                } else if (z != 0 && j == divNumMax) {
                    maxNumNew = i;
                    return maxNumNew;

                }
            }

        }
        return 10000;
    }


    private boolean findPalindrome(int firstPrime, int secondPrime) {

        int resultOfMath = firstPrime * secondPrime;

        String ltrResult = Integer.toString(resultOfMath);
        String rtlResult = new StringBuffer(ltrResult).reverse().toString();

        if (ltrResult.equals(rtlResult)) {

            palind = resultOfMath;
            return false;

        } else {
            return true;
        }
    }
}


Скриншот полученного результата на эмуляторе:



Ломаю голову где ошибся, что упустил. Не прошу делать за меня ТЗ, но не хочу оставлять
позади какую-то неразобранную проблемму.
    

Ответы

Ответ 1

Ваше целое несколько раз завернулось вокруг максимального значения int - 2,147,483,647.

Проверьте:

99923 * 87541 = 8 747 359 343


А также:

На какую цифру должно заканчиваться произведение Ваших двух простых чисел?


Ответ 2

решето работает отлично, ранее искал все простые числа в диапазоне 0- 10 000 000
ушло примерно 15 секунд на планшете. главное правильно написать алгоритм.

возможно я не верно понял ваш алгоритм (прошу исправить меня)

почему второй цикл идет по увеличению параметра, а не от большего к меньшему?

for (j = 3; j <= divNumMax; j++) {



есть нюанс: рассмотрим ту же задачу, но в диапазоне 0-15, пока отбросим условие палиндрома
(здесь оно  не играет роли).

a = 13; b = 2; a*b = 26


но есть и другие простые числа произведение которых даст значительно больше результат?
11*13 > 26


Ответ 3

Вот правильный ответ на задачу, также встречал на собесе:
палиндром - 999949999
множитель1 - 33211
множитель2 - 30109
Реализовал алгоритм так:
Метод поиска наибольшего палиндрома (на входе список простых чисел)

static void palindrome(ArrayList primeNumbers) {
    long palindrome = 0;
    long multiplier1 = 0;
    long multiplier2 = 0;
    for (int j = 0; j < primeNumbers.size(); j++) {
        for (int k = 0; k < primeNumbers.size(); k++) {
            long i = (long) primeNumbers.get(j) * (long) primeNumbers.get(k);
            if (palindromeCheck(i)) {
                if (i > palindrome) {
                    palindrome = i;
                    multiplier1 = primeNumbers.get(j);
                    multiplier2 = primeNumbers.get(k);
                }
            }
        }
    }
    System.out.println("palindrome = " + palindrome
            + "\nmultiplier1 = " + multiplier1
            + "\nmultiplier2 = " + multiplier2);
}  


Метод поиска простых чисел (на входе максимальное и минимальное значения из проверяемого
диапазона чисел):  

static ArrayList eratosthenesPrimeNumbers(int max, int min) {
    ArrayList primeNumbers = new ArrayList<>();
    boolean[] array = new boolean[max];

    for (int i = 2; Math.pow(i, 2) <= max; i++) {
        if (!array[i]) {
            for (int j = (int) Math.pow(i, 2); j < max; j += i) {
                array[j] = true;
            }
        }
    }
    for (int i = max - 1; i >= min; i--) {
        if (!array[i]) {
            primeNumbers.add(i);
        }
    }
    return primeNumbers;
}  


Проверка на то, что найденное число является палиндромом (на входе проверяемое число):  

static boolean palindromeCheck(long i) {
    char[] palindrome = String.valueOf(i).toCharArray();
    int fromBegin = 0;
    int fromEnd = palindrome.length - 1;
    while (fromBegin < fromEnd) {
        if (palindrome[fromBegin] == palindrome[fromEnd]) {
            fromBegin++;
            fromEnd--;
        } else return false;
    }
    return true;
}


Да и еще забыл написать, что эти методы надо вызывать :)
У меня это сделано так:  

public class Main {
static final int MAX_MULTIPLIER = 99999;
static final int MIN_MULTIPLIER = 10000;

public static void main(String[] args) {

    ArrayList primeNumbers2 = new ArrayList<>(eratosthenesPrimeNumbers(MAX_MULTIPLIER,
MIN_MULTIPLIER));
    palindrome(primeNumbers2);
}


и дальше реализация методов...


Ответ 4

Немного вник в алгоритм. По моему, он работает неправильно уже здесь:

 while (isNotPalind) {

            if (sPM <= fPM && sPM > minNum) {
                sPM = findMaxPrimeNumber(sPM - 2);
                isNotPalind = findPalindrome(fPM, sPM);

            } else if (sPM <= minNum) {
                fPM = findMaxPrimeNumber(fPM - 2);
                sPM = fPM;
            }


        }


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

Возьмем отвлеченный от этого пример прогонки от 10 до 1 возможных произведений всех
чисел.

По твоему алгоритму идем по 1-му кругу:

10*10, 10*9 , 10*8, 10*7.... <- и сразу выводим первый попавшийся палиндром

далее второй круг:

9*9, 9*8, 9*7... <- или уж тут сразу выводим первый попавшийся палиндром

далее третий:

8*8, 8*7, 8*6...


И так далее...

Допустим на 1-ом круге 10*2 - это палиндром (гипотетически!)

Также допустим на 2-ом круге 9*8 - это тоже палиндром (гипотетически!)

Но твоя программа выведет 10*2 (несмотря на то что 9*8 больше чем 10*2)

То есть первое попавшееся - это не вариант.
Надеюсь автор меня понял и поправит если я не прав.


Ответ 5

условие задачи подразумевало произведение двух простых пятизначных чисел.
алгоритм работает для двух, трех, четырехзначных чисел. но в упор отказывается работать
для 5-ти. в чем тут ошибка?

public class Palindrome {
    private static final boolean reverse(long value) {
        String str = String.valueOf(value);
        return str.equals(new StringBuilder(str).reverse().toString());
    }

    private static final boolean isPrime(int n) {
        int i;
        for (i = 2; i <= n / 2; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }


    public static void main(String[] args) {

        int i = 0;
        int maxPrimeNumber = 99971;
        int minPrimeNumber = 10007;

        outer:
        for (i = maxPrimeNumber; i >= minPrimeNumber; i--) {
            for (int j = maxPrimeNumber; j >= minPrimeNumber; j--) {

                if (isPrime(i) && isPrime(j)) {
                    long product = j * i;
                    if (reverse(product)) {
                        System.out.printf("%d * %d = %d%n", i, j, product);
                        break outer;
                    }
                }
            }
        }
    }
}