Liczby pierwsze na SPOJ

Wyrzuca mi że za długo działa, jak to można zrobić szybciej ? ;/

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner skan = new Scanner(System.in);
        int n,liczba;
        n = skan.nextInt();
        String wynik="";
        for(int i=0; i<n;i++) {
            liczba=skan.nextInt();
            if(liczba==1) wynik=wynik+"NIE\n";
            else if((liczba==2)||(liczba==3)||(liczba==5)||(liczba==7)) wynik=wynik+"TAK\n";
            else if((liczba%2==0)||(liczba%3==0)||(liczba%5==0)||(liczba%7==0)){
                wynik=wynik+"NIE\n";
            }else wynik=wynik+"TAK\n";
        }

       
	System.out.print(wynik);

    }

}

po pierwsze chyba zły dział, po drugie to nie ma szans zadziałać, po trzecie skoro nie przechodzi ze względu na przekroczenie czasu, to pewnie dla pewnych danych nie wyrzuca nic. Alternatywą dla ostatniego jest tylko "nie da się tego zrobić w javie bez przekroczenia limitu", prawidłowy algorytm potrwa dużo dłużej, patrz http://pl.wikipedia.org/wiki/Sito_Eratostenesa. Szybciej już tylko Liniówka, czyli jeśli liczba ta to "na sztywno" wypisz TAK lub NIE (zależnie od liczby) bez liczenia czegokolwiek.

1. Wpisz te liczby (które trzeba zbadać) do tablicy.
2. Znajdź maksymalną z nich
3. Zbuduj sito Eratostenesa do maksymalnej liczby włącznie.
4. Buduj wynik następująco: wynik+=(Sito[Tb[i]]?"TAK\n":"NIE\n") ; System.out.print(Sito[Tb[i]]?"TAK\n":"NIE\n");

na pewno stałą czasową poprawisz sobie znacząco tak:

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
 
        Scanner skan = new Scanner(System.in);
        int n,liczba;
        n = skan.nextInt();
        for(int i=0; i<n;i++) {
            liczba=skan.nextInt();
            if(liczba==1) System.out.print("NIE\n");
            else if((liczba==2)||(liczba==3)||(liczba==5)||(liczba==7)) System.out.print("TAK\n");
            else if((liczba%2==0)||(liczba%3==0)||(liczba%5==0)||(liczba%7==0)){
                System.out.print("NIE\n");
            }else System.out.print("TAK\n");
        }
    }
 
}

Jesteś pewien, że w tym zadaniu są tylko do sprawdzania liczby mniejsze od 10?

Prawidłowo to powinieneś znaleźć sobie wszystkie liczby pierwsze w zakresie 1 - zakres używając np. algorytmu sita erastotenesa, następnie po prostu sprawdzać czy dana liczba jest pierwsza. Z sita powinna wyjść Ci ładna tablica bool-i więc możesz z niej skorzystać. Liczby pierwsze powinieneś wygenerować DOKŁADNIE RAZ na początku programu

Akurat na SPOJu wyniki podaje się od razu, bo może czekać z następnym testem na wynik poprzedniego. No chyba że to zadanie jakieś szczególne. W każdym razie mi w c++ przeszło sprawdzanie wszystkich liczb mniejszych od badanej, więc limit czasu raczej dużym problemem nie jest.