Jak pominąć wczytywanie entera?

Odpowiedz Nowy wątek
2016-03-05 11:48

Rejestracja: 4 lata temu

Ostatnio: 3 lata temu

0

Witajcie!

Próbuję rozwiązać to zadanie:
http://www.spoj.com/problems/PRIME1/

Działa mi prawie wszystko poza jednym wyjątkiem: Ostatnia pętla oczekuje na enter i w związku z tym kod nie jest akceptowany (błąd NZEC). Jak mogę poradzić sobie z tym problemem?
Próbowałem szukać w google i tutaj, ale nawet nie wiem za bardzo jakie hasło wpisywać, bo nic konstruktywnego nie mogłem znaleźć.

import java.util.Scanner;

public class PRIME1 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long t=in.nextInt();
        for (long k=0; k<t; k++){
            System.out.println("K= " + k);
            long m=in.nextLong();
            long n=in.nextLong();
            in.reset();
            System.out.println("M= " + m);
            System.out.println("N= " + n);
            long[] tab = new long[(int) (n+1)];
            for (long i=2; i<=n; i++){
                tab[(int)i]=i;
            }
                        // Sito Eratostenesa
            for (long i=2; i*i<=n; i++) {
                if (tab[(int)i] != 0) {
                    long j = i+i;
                    while (j<=n) {
                        tab[(int)j] = 0;
                        j += i;
                    }
                }
            }
            for (long i=m; i<=n; i++){
                if (tab[(int)i]!=0) {
                    System.out.println(i);
                }       
            }
            System.out.println("");
        }
    }
}

Pozostało 580 znaków

2016-03-05 12:18

Rejestracja: 4 lata temu

Ostatnio: 26 minut temu

Lokalizacja: Hong Kong

0

chyba nie dales kompletnego kodu bo nie widze tu nigdzie czekania na enter. w takim wypadku rozwiazaniem by bylo usuniecie linijki czekajacej na enter ;)
pare uwag bez szczegolowej analizy kodu:

  • robisz sito przy kazdej nowej parze liczb, nie ma szans zeby takie podejscie przeszlo czasowo
  • po co w ogole uzywasz long i rzutujesz na int? po prostu uzywaj int)
  • pogogluj jak przyspieszyc std in/out w javie, to co robisz jest bardzo nieefektywne (pokombinuj np z buforowaniem, z tego co pamietam duzo tez daje napisane wlasnego parsera do intow ze strumienia bajtow, sorry ale jdk nie blyszczy tutaj)

Pozostało 580 znaków

2016-03-05 16:02

Rejestracja: 4 lata temu

Ostatnio: 3 lata temu

0

Jednak okazało się, że problem leży w zupełnie innym miejscu. Byłem pewny, że błąd NZEC wynikał z niekończącego się programu (czyli ten brak entera, o którym pisałem na początku :-) ).
Natomiast okazało się, że mam problem z pamięcią - powyżej pewnego zakresu wyskakuje mi błąd java.lang.OutOfMemoryError: Java heap space. Wynika on z błędu rozmiaru tablicy. Mógłbym zainicjować tablicę o max rozmiarze przedziału (100 000), ale nie bardzo wiem jak w takim wypadku znaleźć liczby pierwsze. Proszę o pomoc!

Zmieniłem trochę myślenie i wykonuję sito tylko raz. Wyświetlanie nie jest problemem, bo max przedział to 100 000 co daje ~10 000 liczb pierwszych.

Oto mój kod:

import java.util.Scanner;

public class PRIME1 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t=in.nextInt();
        int[] m = new int[t];
        int[] n = new int[t];
        for (int k=0; k<t; k++){
            m[k]=in.nextInt();
            n[k]=in.nextInt();
        }

        int max = m[0];
        for (int i=0; i<t; i++){
            if (n[i]>max){
                max = n[i];
            }
        }
        //Sito Eratostenesa
        int[] sito = new int[max+1];
        for (int i=2; i<=max; i++){
                sito[i]=i;
        }
        for (int i=2; i*i<=max; i++) {
            if (sito[i] != 0) {
                int j = i+i;
                while (j<=max) {
                    sito[j] = 0;
                    j += i;
                }
            }
        }   

        //Wyswietlanie
        for (int i=0; i<t; i++){
            for(int j=m[i]; j<=n[i]; j++){
                if (sito[j]!=0){
                    StringBuilder sb = new StringBuilder();
                    sb.append(sito[j]).append("\n");
                    String str = sb.toString();
                    System.out.print(str);
                }
            }
            System.out.println("");
        }
    }
}
edytowany 2x, ostatnio: Tomekaa, 2016-03-05 16:43

Pozostało 580 znaków

2016-03-05 16:39

Rejestracja: 7 lat temu

Ostatnio: 8 godzin temu

0

Jedno jest pewne: tworzysz sito Eratostenesa tylko raz.
Tylko jednokrotnie.
Żeby nie komplikować możesz utworzyć go dla przedziału <1, 1000000000> na samym początku.
EDIT: Po Twoim kodzie widzę, że sprytniej szukasz maksymalnej liczby n. Nie potrzeba dwóch pętli for. Możesz to załatwić w jednej, np. tak.


int max = 0;
for (int k=0; k<t; k++) {
    m[k]=in.nextInt();
    n[k]=in.nextInt();
    if (n[k] > max) max = n[k];
}

Lepiej to robić na kolekcjach niż na tablicach statycznych.
Możesz wykorzystać do tego coś takiego jak TreeSet, by szybko eliminować niepotrzebne liczby.
Sito zwraca zbiór liczb pierwszych w porządku niemalejącym (primeSet).

Następnie wielokrotnie:
dla liczby m zwracasz i wypisujesz po kolei cały podzbiór aż do n</code> (iterujesz poprimeSet.tailSet(m)po kolei aż do końca lub natrafienia na <code>n).

Możesz wykorzytać BufferedReadera oraz InputStreamReadera zamiast Scannera dla czasu.

EDIT:
Lepiej to robić na kolekcjach (proponuję TreeSet), bo marnujesz miejsce i czas na zera w tabeli sito.

edytowany 4x, ostatnio: grzzpo, 2016-03-05 16:57

Pozostało 580 znaków

2016-03-06 11:17
Moderator

Rejestracja: 11 lat temu

Ostatnio: 1 rok temu

0

Lepiej tworzyć sito po wczytaniu danych. Może się przecież okazać, że wystarczy sito dla przedziału <1, 130>.


To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell

Pozostało 580 znaków

Odpowiedz

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0