(SPOJ) Selos - Solution

Link to the problem: http://br.spoj.com/problems/SELOS11/

The solution below has a special case that checks if the number is less than 4, which indicates that it is not possible to form a rectangle with more than one row and one column. For the other numbers, we find the square root of this number, and we check if the number is divisible for any other number between 2 and the square root.

We do not check this condition between 2 and the number because the maximum number can be 10,000,000,000, which would exceed the time limit. Using the square root, we decrease considerably the number of operations.


import java.io.*;
import java.util.*;

class Main {
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
      
        String line = br.readLine();
        long number = Long.parseLong(line);
        if (number < 4) {
            bw.write("N\n");
        }
        else {
            boolean yes = false;
            long sqrt = (long)Math.sqrt(number);
            for (long i = 2; i <= sqrt; i++) {
                if (number%i == 0) {
                    bw.write("S\n");
                    yes = true;
                    break;      
                }
            }
            if (!yes) {
                bw.write("N\n");
            }
        }
          
        br.close();
        bw.flush();
        bw.close();
       
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
      
        System.exit(0);
    }
}