Labels

Project Euler #72: Counting fractions

Question
Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.
If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
It can be seen that there are 21 elements in this set.
How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000?

Answer : 303963552391

Hacker Rank Problem

Solution


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.Scanner;

public class Solution {
    
    public static void main(String[] args) {
        int N = 1000000;
        int[] phi = new int[N + 1];
        for(int i = 0; i < phi.length; i++) {
            phi[i] = i;
        }
        for(int i = 2; i <= N; i++) {
            if(phi[i] == i) {
                for(int k = 1; k * i <= N; k++) {
                    phi[k * i] -= phi[k * i] / i;
                }
            }
        }
        long[] sums = new long[phi.length];
        for(int i = 2; i <= N; i++) {
            sums[i] = sums[i - 1] + phi[i];
        }
        try(Scanner sc = new Scanner(System.in)) {
            int T = sc.nextInt();
            while(T > 0) {
                N = sc.nextInt();
                System.out.println(sums[N]);
                T--;
            }
        }
    }
}
Labels:

Comments

Post a Comment

Popular Posts