مساله:
آرایه ای از اعداد صحیح مثبت و منفی به شما داده می شود:
I= [i1,..,in]
شما باید آرایه P را به فرم زیر ایجاد کنید:
[ [p, sum of all ij of I for which p is a prime factor (p positive) of ij] ...]
آرایه P باید بر اساس اعداد اول مرتب سازی شود. در آخر باید نتیجه به صورت یک رشته نمایش داده شود.
مثال:
I = {12, 15}; // result = "(2 12)(3 27)(5 15)"
اعداد [2,3,5] لیست اعداد اولی است که در این آرایه استفاده شده است.
نکته:
این امکان وجود دارد که اگر اعداد منفی هم داشته باشیم، جمع اعداد 0 شود.
Description:
Given an array of positive or negative integers
I= [i1,..,in]
you have to produce a sorted array P of the form
[ [p, sum of all ij of I for which p is a prime factor (p positive) of ij] ...]
P will be sorted by increasing order of the prime numbers. The final result has to be given as a string in Java, C#, C, C++ and as an array of arrays in other languages.
Example:
I = {12, 15}; // result = "(2 12)(3 27)(5 15)"
[2, 3, 5] is the list of all prime factors of the elements of I, hence the result.
Notes:
It can happen that a sum is 0 if some numbers are negative!
Example: I = [15, 30, -45] 5 divides 15, 30 and (-45) so 5 appears in the result, the sum of the numbers for which 5 is a factor is 0 so we have [5, 0] in the result amongst others.
In Fortran – as in any other language – the returned string is not permitted to contain any redundant trailing whitespace: you can use dynamically allocated character strings.
راه حل:
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class SumOfDivided {
public static String sumOfDivided(int[] l) {
final int maxValue = Arrays.stream(l).map(num -> Math.abs(num)).max().getAsInt();
return eratosteneSieve(maxValue).stream()
.reduce("",
(resultString, primeNum) -> {
List<Integer> divisibleNum = Arrays.stream(l).filter(num -> num % primeNum == 0).boxed().collect(Collectors.toList());
return divisibleNum.size() > 0
? resultString + String.format("(%d %d)", primeNum, divisibleNum.stream().mapToInt(Integer::intValue).sum())
: resultString;
},
(not, used) -> null);
}
public static List<Integer> eratosteneSieve(final int x) {
final List<Integer> candidates = IntStream.rangeClosed(2, x).boxed().collect(Collectors.toList());
return candidates.stream()
.filter(num -> num <= Math.sqrt(x))
.reduce(candidates,
(resList, currNum) -> resList.stream()
.filter(num -> num % currNum != 0 || num.equals(currNum))
.collect(Collectors.toList()),
(not, used) -> null);
}
}import java.lang.Math;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.TreeMap;
import java.util.HashMap;
import java.util.stream.Collectors;
public class SumOfDivided {
/*
* We use a cache of already known primes to minimize double computation.
*/
private static SortedSet<Integer> primeCache = new TreeSet<>();
private static Map<Integer, Integer> map = new HashMap<>();
public static String sumOfDivided(int[] l) {
initalize();
for(int i=0; i<l.length; i++) {
int absNum = Math.abs(l[i]);
updatePrimeCache(absNum);
updateMap(l[i]);
}
return convertMapToString();
}
private static void initalize(){
map = new HashMap<>();
if(primeCache.isEmpty()){
primeCache.add(2);
}
}
/*
* We update the prime cache so it contains all primes up to number.
*/
private static void updatePrimeCache(int number) {
Integer largestKnownPrime = primeCache.last();
if(largestKnownPrime > number) {
return;
}
for(int p=largestKnownPrime+1; p <= number; p++) {
if(isPrime(p)) {
primeCache.add(p);
largestKnownPrime = p;
}
}
}
private static boolean isPrime(int p) {
for(int i=2; i<=Math.sqrt(p); i++) {
if(p%i == 0) return false;
}
return true;
}
private static void updateMap(int num) {
for(Integer prime: primeCache) {
if(num%prime == 0) {
Integer sum = map.getOrDefault(prime, 0);
sum += num;
map.put(prime, sum);
}
}
}
private static String convertMapToString() {
TreeMap<Integer, Integer> sortedMap = new TreeMap(map);
return sortedMap.entrySet()
.stream()
.map(entry -> "(" + entry.getKey() + " " + entry.getValue() + ")")
.collect(Collectors.joining(""));
}
}import java.util.*;
import java.util.stream.*;
import static java.util.stream.Collectors.*;
import static java.util.Arrays.*;
public class SumOfDivided {
public static String sumOfDivided(int[] l) {
return generatePrimeNumbersClosed(stream(l).max().orElse(0))
.mapToObj(it -> new Object(){ int primeNumber = it, sum = stream(l).filter(n -> n % it == 0).sum(); })
.filter(it -> it.sum > 0)
.map(it -> String.format("(%d %d)", it.primeNumber, it.sum))
.collect(joining(""));
}
private static IntStream generatePrimeNumbersClosed(int n) {
BitSet composited = new BitSet();
for(int i = (int) Math.sqrt(n); i >= 2; i--) for(int m = i * i; m <= n; m += i) {
composited.set(m);
}
return IntStream.rangeClosed(2, n).filter(it -> !composited.get(it));
}
}
import java.util.*;
import java.util.stream.*;
import static java.util.stream.Collectors.*;
import static java.util.Arrays.*;
public class SumOfDivided {
public static String sumOfDivided(int[] l) {
return generatePrimeNumbersClosed(stream(l).max().orElse(0))
.mapToObj(it -> new Object(){ int primeNumber = it, sum = stream(l).filter(n -> n % it == 0).sum(); })
.filter(it -> it.sum > 0)
.map(it -> String.format("(%d %d)", it.primeNumber, it.sum))
.collect(joining(""));
}
private static IntStream generatePrimeNumbersClosed(int n) {
BitSet composited = new BitSet();
for(int i = (int) Math.sqrt(n); i >= 2; i--) for(int m = i * i; m <= n; m += i) {
composited.set(m);
}
return IntStream.rangeClosed(2, n).filter(it -> !composited.get(it));
}
}
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;
public class SumOfDivided {
public static String sumOfDivided(int[] l) {
StringBuilder stringBuilder = new StringBuilder();
Set<Integer> allPrimeFactorsForElementsOfl = findAllPrimeFactorsForElementsFromArr(l);
for (Integer primeFactor : allPrimeFactorsForElementsOfl) {
int sum = 0;
for (Integer element : l) {
if (isPrimeFactor(primeFactor, element)) {
sum += element;
}
}
stringBuilder.append("(" + primeFactor + " " + sum + ")");
}
return stringBuilder.toString();
}
private static Set<Integer> findAllPrimeFactorsForElementsFromArr(int[] numbers) {
Set<Integer> primeFactors = new TreeSet<Integer>();
for (int number : numbers) {
primeFactors.addAll(findPrimeFactors(Math.abs(number)));
}
return primeFactors;
}
private static Set<Integer> findPrimeFactors(int numberFromI) {
Set<Integer> primeFactors = new HashSet<Integer>();
for (int i = 2; i <= numberFromI; i++) {
while (numberFromI % i == 0) {
primeFactors.add(i);
numberFromI /= i;
}
}
return primeFactors;
}
private static boolean isPrimeFactor(int primeFactor, int numberTobeChecked) {
return numberTobeChecked % primeFactor == 0;
}
}
import java.util.Arrays;
import java.util.OptionalInt;
import java.util.stream.IntStream;
public class SumOfDivided {
public static String sumOfDivided(int[] numbers) {
int maxValue = Arrays.stream(numbers).map(Math::abs).max().getAsInt();
boolean[] eratosteneSieve = new boolean[maxValue];
StringBuilder result = new StringBuilder(4*maxValue*numbers.length);
IntStream.rangeClosed(2, maxValue)
.filter(num-> !eratosteneSieve[num-2])
.forEach(prime->{
for(int i=2; prime*i <= maxValue; i++){
eratosteneSieve[prime*i-2] = true;
}
OptionalInt sum = Arrays.stream(numbers).filter(num-> num % prime == 0).reduce(Integer::sum);
if(sum.isPresent()){
result.append("(").append(prime).append(" ").append(sum.getAsInt()).append(")");
}
});
return result.toString();
}
}
