#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(ArrayListprimeNumbers) { 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; } } } } } }
