Jak pominąć wczytywanie entera?

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("");
		}
	}
}
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)
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("");
		}
	}
}
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 po primeSet.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.

0

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

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