We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Project Euler #72: Counting fractions
Project Euler #72: Counting fractions
+ 0 comments javascript solution ?
+ 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--; } } }
}
+ 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--; } } }
}
+ 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--; } } }
}
+ 0 comments Well, if you already solved problem 69-70, then you can easily pass all testcases by using dictionary/hash to store sums.
If you did not, then this Python Euler totient function can help
Load more conversations
Sort 15 Discussions, By:
Please Login in order to post a comment