Cod sursa(job #1938548)

Utilizator lucibitLucian Onea lucibit Data 24 martie 2017 21:22:40
Problema Fractii Scor 30
Compilator java Status done
Runda Arhiva de probleme Marime 2.17 kb
import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String[] args) {
        try {
            //READING PART
            BufferedReader br = new BufferedReader(new FileReader("fractii.in"));
            int n = Integer.valueOf(br.readLine());
            br.close();
            int res = 1, i,j;
            boolean[] notPrime = new boolean[n+1];
            List<Integer> primes = new ArrayList<Integer>();
            double sqrt = Math.sqrt(n);
            for (i = 2; i < sqrt; i++ ) {
                j = i * 2;
                while ( j <= n ) {
                    notPrime[j] = true;
                    j += i;
                }
            }

            for ( i = 2; i <=n ; i++) {
                if (!notPrime[i]) {
                    primes.add(i);
                }
            }


            for (i = 2; i <= n; i++) {
                double sqrt_f  = Math.sqrt(i);
                int t = i;
                int euler = 1, prime;
                j = 0;
                int k = 0;
                if (!notPrime[i]) {
                    euler = i - 1;
                } else {
                    while (t >= 1 && j < primes.size() && primes.get(j) <= i) {

                        prime = primes.get(j);
                        //System.out.print(prime);
                        if (t % prime == 0) {
                            k++;
                            t /= prime;
                        } else {
                            k = 0;
                            j++;
                        }
                        if (k != 0) {
                            euler *= k == 1 ? (prime - 1) : prime;
                        }
                    }
                }
                res = res + 2 * euler;
                //System.out.println(i +" -> " + "factors:  " + euler + " res: "+ res );
            }

            BufferedWriter bw = new BufferedWriter(new FileWriter("fractii.out"));
            bw.write(String.valueOf(res));
            bw.close();

        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

}