Liczby Pół pierwsze

Question

Treść zadania:

Liczbą półpierwszą nazywamy taką liczbę, która jest iloczynem dwóch liczb pierwszych. Sprawdź czy podana liczba w reprezentacji binarnej jest liczbą półpierwszą.

Tu jest moja metoda która powinna to sprawdzać

static boolean checkIfIsSemiFirstNumber(String str) {

        int decNum = Integer.parseInt(str, 2); // zamiana na dziesietna liczbe

        List<Integer> primeNumbers = new ArrayList<>();
// generowanie liczb pierwszych
        for (int i = 1; i <= decNum ; i++) {
            int counter = 0;

            for (int j = 1; j <= i; j++) {

                if (i % j == 0) counter++;
            }

            if (counter == 2) primeNumbers.add(i);
        }
// sprawdzanie
        for (int i=0; i<primeNumbers.size(); i++) {

            for (int j = 0; j < primeNumbers.size() ; j++){
                if (primeNumbers.get(i)*primeNumbers.get(j) == decNum) return true;
            }
        }
        return false;
    }

W rozwiązaniu chodziło mi o to, żeby wygenerować listę liczb pierwszych od 1 do n i następnie mnożąc wszystkie przez wszystkie sprawdzić czy któraś para jest równa sprawdzanej liczbie. Nie uznałbym tego rozwiązania za seksowne ale powinno działać, a nie mogę znaleźć tutaj błędu.

Comments

Seksowności rozwiązania oceniać nie będę - wole podziwiać inne cuda natury :). Jeśli chcesz pomocy, to prosiłbym o podanie danych przykładowych oraz wyników zwracanych przez program - w momentach w których się myli i w których wykonuje poprawnie.

Answer 1

"generowanie liczb pierwszych" Dziwnie to brzmi z matematycznego punktu widzenia ;D

Wiesz Hipoteza Riemanna, setki lat z próbą odkrycia sekretu i (wzoru?) liczb pierwszych... Takie tam : )

Comments

Mówimy tu o generowaniu liczb pierwszych z określonego przedziału [2 ... n]. Do tego można zastosować sito erosteresa. Wiadomo, ze nie mówimy o przypadkach, gdzie „n” jest równe bardzo dużej liczbie. W zadaniu musisz wykryć to tylko dla jednej liczby. Dlatego sito i sposób generowania zbioru, raczej sensu nie ma. No chyba ze wybierał będziesz kilka razy i masz zdefiniowany zakres zbioru. Jeżeli mowa tylko o jednej liczbie, to w pętli po koleii sprawdzaj jej dzielniki. Licz ilość ich wystąpień. Jak będzie ich więcej niż dwa, to przerwij pętle i to nie bedzie liczba pierwsza. Ilość kroków pętli możesz zmniejszyć o pierwiastek z danej liczby. Jeżeli liczba będzie pierwsza, to sprawdź drugi warunek

---

To są klasyczne metody. Z tego co kajaze, to jest binarna metoda na szukanie liczb pierwszych.