Проект Эйлера # 49 Java

Question

Вопрос заключается в том -

арифметическая последовательность, 1487, 4817, 8147, в которой каждый из членов возрастает по 3330, необычен двумя способами: (я), каждый из три члена являются простыми, и (ii) каждое из 4-значных чисел являются перестановками друг на друга.

Нет арифметических последовательностей, состоящих из трех 1-, 2- или 3-значных чисел , имеющих это свойство, но есть еще одна 4-значная последовательность увеличения .

Какое 12-значное число вы создаете, объединив три термина в этой последовательности?

Я написал этот код -

package Problems; 

import java.util.ArrayList; 
import java.util.LinkedList; 

public class Pro49 { 

    private static boolean isPrime(int n){ 
     if(n%2 == 0) return false; 

     for(int i = 3; i<= Math.sqrt(n); i++){ 
      if(n%i == 0) return false; 
     } 

     return true; 
    } 

    private static boolean isPerm(int m, int n){ 
     ArrayList<Integer> mArr = new ArrayList<>(); 
     ArrayList<Integer> nArr = new ArrayList<>(); 

     for(int i = 0; i<4; i++){ 
      mArr.add(m%10); 
      m /= 10; 
     } 

     for(int i = 0; i<4; i++){ 
      nArr.add(n%10); 
      n /= 10; 
     } 

     return mArr.containsAll(nArr); 
    } 

    public static void main(String[] args) { 

     LinkedList<Integer> primes = new LinkedList<>(); 

     for(int i = 1001; i<10000; i++){ 
      if(isPrime(i)) primes.add(i); 
     } 


     int k = 0; 
     boolean breaker = false; 
     for(int i = 0; i<primes.size() - 2; i++){ 
      for(int j = i + 1; j<primes.size() - 1; j++){ 
       if(isPerm(primes.get(i), primes.get(j))) { 
        k = primes.get(j) + (primes.get(j) - primes.get(i)); 

        if(k<10000 && primes.contains(k) && isPerm(primes.get(i), k)) { 
         System.out.println(primes.get(i) + "\n" + primes.get(j) + "\n" + k); 
         breaker = true; 
         break; 
        } 

       } 
       if(breaker) break; 
      } 
      if(breaker) break; 
     } 


    } 

} 

Я добавил печати линию System.out.println(primes.get(i) + "\n" + primes.get(j) + "\n" + k); проверить номера. Я получил 1049, 1499, 1949, которые ошибаются. (По крайней мере, 1049 ошибочно).

Может ли кто-нибудь указать, где мой код/​​логика не так? Любая помощь приветствуется.

Answer 1

Я думаю, что ваша логика идет не так, как ваш метод isPerm. Вы используете AbstractCollection#containsAll, который, AFAIK, проверяет только, находятся ли параметры в коллекции хотя бы один раз.

т.е. он в основном делает

for(E e : collection) 
    if(!this.contains(e)) return false; 
return true; 

Поэтому, например, 4999 будет перестановка 49, потому что 49 содержит 4 и 9 (в то время как он явно не основано на вашем примере).

---

Причина, почему ваш метод, кажется, работает для этих значений является то, что вы зацикливание определенное количество времени - то есть 4. Для ряда, как 49 вы будете в конечном итоге с {9, 4, 0, 0} вместо {9, 4}. Сделайте что-то вроде этого:

while(n != 0) { 
    nArr.add(n%10); 
    n /= 10; 
} 

и вы получите правильные цифры List с (. И видеть, что containsAll не будет работать)

Добавить ограничение 4-значного в другом месте (., Например, в цикле)

---

Возможно, вы смогли проверить происшествия на цифру. Например:

int[] occurrencesA = new int[10], occurrencesB = new int[10]; 
for(; m != 0; m /= 10) 
    occurrencesA[m % 10]++; 
for(; n != 0; n /= 10) 
    occurrencesB[n % 10]++; 
for(int i = 0; i < 10; i++) 
    if(occurrencesA[i] != occurrencesB[i]) return false; 
return true; 

Answer 2

я нашел возможную альтернативу для isPerm

private static boolean isPerm(int m, int n){ 
     ArrayList<Integer> mArr = new ArrayList<>(); 
     ArrayList<Integer> nArr = new ArrayList<>(); 

     final String mS = Integer.toString(m); 
     final String nS = Integer.toString(n); 

     if(mS.length() != nS.length()) return false; 

     for(int i = 0; i<mS.length(); i++){ 
      mArr.add(m%10); 
      m /= 10; 
     } 

     for(int i = 0; i<nS.length(); i++){ 
      nArr.add(n%10); 
      n /= 10; 
     } 

     return (mArr.containsAll(nArr) && nArr.containsAll(mArr)); 
    } 

Это дает мне правильный ответ. Другая альтернатива вывешена другим человеком ниже.