Project Euler #72: Counting fractions Discussions |

Sort by

recency

|

16 Discussions

|

1 year ago+ 1 comment

Python Solution.

lookup=[i for i in range(10**6+1)]
for i in range(2,10**6+1):
    if lookup[i]==i:
        for j in range(i,10**6,i):
            lookup[j]-=lookup[j]//i
for i in range(3,10**6):
    lookup[i]+=lookup[i-1]
t=int(input().strip())
for _ in range(t):
    n=int(input().strip())
    print(lookup[n])

6 months ago+ 0 comments

This was practically identical to my initial approach, but I got a ton of time out errors. So I spent forever trying to optimize and try different approaches, but none of them worked. I saw your comment and tried this way again, and it worked this time. Now it will forever haunt me that I don't know what was different between the first and second attempts.

3 years ago+ 0 comments

javascript solution ?

4 years ago+ 0 comments

All test case pass java 8 ` import java.io.; import java.util.;

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--;
        }
    }
}

}

4 years ago+ 0 comments

All test case pass ` import java.io.; import java.util.;

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--;
        }
    }
}

}

4 years ago+ 0 comments

` import java.io.; import java.util.;

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--;
        }
    }
}

}

Sort by

|

16 Discussions

|

Cookie support is required to access HackerRank

Please signup or login in order to view this challenge