Pages

Wednesday 10 October 2012

UVA - 10699 - Count the factors


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
       
        InputStreamReader isr=new InputStreamReader(System.in);
        BufferedReader br=new BufferedReader(isr);
        StringBuffer sb = new StringBuffer("");
        String m = "";
        boolean[] arr=sievePrime(1000*1000);
        while ((m=br.readLine())!=null) {
            if("0".equals(m))
                break;
            int x=Integer.parseInt(m);
            sb.append(x).append(" : ").append(countF(x, arr)).append("\n");
        }
        System.out.print(sb);
    }
   
     static boolean[] sievePrime(int x) {
        boolean[] notPrime = new boolean[x + 1];
        notPrime[0] = true;
        notPrime[1] = true;
        for (int i = 2; i * i < x + 1; i++) {
            if (!notPrime[i]) {
                for (int j = i; i * j < x + 1; j++) {
                    notPrime[i * j] = true;
                }
            }
        }
        return notPrime;
    }
    
     static int countF(int x,boolean[]  arr){
        int count=0,i;
        for(i=1;i<Math.sqrt(x);i++){
           if(x%i==0){
               if(!arr[i])
                count++;
                if(x/i!=i && !arr[x/i]){
                    count++;
                }
           }
        }
        return count;
    }
}

No comments:

Post a Comment