Hackerrank - Equations - Pavol Pidanič

Popis problému
Celý popis zadania sa nacháza – Hackerrank.

Riešenie
Riešenie podľa tohto alebo tohto.

Vytvoril som riešenie v týchto programovacích jazykoch:

Java
JavaScript
Ruby
Scala

Všetky riešenia sú dostupné aj na mojom GitHub profile.

Java

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

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

'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));

'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

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

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

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

puts result % 1000007

Scala

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

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

}

Pavol Pidanič

Dokážem na 10 prstoch napočítať do 1023

Hackerrank – Equations