Hackerrank – Equations
Problem Statement A description of the problem can be found on Hackerrank. Solution Make prime number factorization of N!. For help click here or here. I created solution in: Java JavaScript Ruby Scala All solutions are also available on my GitHub. Java
|
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
import java.util.*; public class Equations { public static void main(String[] args) { Scanner stdin = new Scanner(System.in); int n = stdin.nextInt(); long result = 1; if(n == 1) { result = 1; } else { List<Integer> primes = eratosthenes(n); for(int i = 0; i < primes.size(); i++) { long prime = primes.get(i); long num = n; long exp = 0; while(num > 0) { long div = num / prime; num /= prime; exp += div; } result *= (2 * exp + 1); result %= 1000007; } } System.out.println(result); stdin.close(); } private static List<Integer> eratosthenes(int num) { List<Integer> result = new LinkedList<>(); boolean[] primes = new boolean[num + 1]; Arrays.fill(primes, true); for(int i = 2; i < primes.length; i++) { if (primes[i]) { long j = i; while (j * i < primes.length) { primes[(int)j * i] = false; j++; } } } for(int i = 2; i < primes.length; i++) { if (primes[i]) { result.add(i); } } return result; } } |
JavaScript
|
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
'use strict'; var eratosthenes = num => { let result = []; let primes = Array(num + 1).fill(true); for(let i = 2; i < primes.length; i++) { if(primes[i]) { let j = i; while(j * i <= primes.length) { primes[j * i] = false; j++; } } } for(let i = 2; i < primes.length; i++) { if (primes[i]) { result.push(i); } } return result; }; const processData = input => { let n = parseInt(input); let result = 1; if(n === 1) result = 1; else { let primes = eratosthenes(n); for(let i = 0; i < primes.length; i++) { let prime = primes[i]; let num = n; let exp = 0; while(num > 0) { let div = parseInt(num / prime); num = (parseInt(num / prime)); exp += div; } result *= (2 * exp + 1); result %= 1000007; } } console.log(result); }; process.stdin.resume(); process.stdin.setEncoding("ascii"); var _input = ""; process.stdin.on("data", input => _input += input); process.stdin.on("end", () => processData(_input)); |
Ruby
|
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 32 33 34 35 36 |
def eratosthenes(num) result = [] primes = Array.new(num + 1, true) for i in 2..primes.length do if primes[i] j = i while j * i <= primes.length do primes[j * i] = false j += 1 end end end for i in 2..primes.length do result << i if primes[i] end return result end input_fact = gets.chomp.to_i result = 1 if input_fact == 1 result = 1 else primes = eratosthenes(input_fact) primes.each do |prime| num = input_fact exp = 0 while num > 0 do div = num / prime num /= prime exp += div end result *= (2 * exp + 1) end end puts result % 1000007 |
Scala
|
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 32 33 34 35 36 37 38 |
import scala.io.Source object Equations extends App { val input = Source.stdin.getLines().toList(0).toInt val result: BigInt = if(input == 1) 1 else equations(input) println(result % 1000007) def sieveEratosthenes(limit: Int): Array[Int] = { val result = Array.fill(limit + 1)(true) for(i <- 2 until result.length) { if(result(i)) { var j: BigInt = i while(j * i < result.length) { result(j.toInt * i) = false j += 1 } } } result.indices.filter(i => i > 1 && result(i) == true).toArray } def equations(input: Int): BigInt = { var result: BigInt = 1 val primes = sieveEratosthenes(input) primes.foreach(prime => { var num = input var exp = 0 while (num > 0) { val div = num / prime num /= prime exp += div } result *= (2 * exp + 1) }) return result } } |