PPRIME- Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Vikas Yadav
Tester: Priyam
Editorialist: Vikas Yadav

DIFFICULTY:

EASY

PREREQUISITES:

Array / List
Prime Factor
Sorting Algorithm

PROBLEM:

Find the descending order of a given unsorted array of natural number after finding the sum of all prime factors for each element.

QUICK EXPLANATION:

First find the sum of prime factors for each element and store in an array. Sort the array in descending order using any sorting algorithm.

EXPLANATION:

Prime number is a natural number greater than 1 having only two factors, 1 and itself.
In this problem we just have to calculate the prime factor of each number and sum up separately and store in that place where that number was present at given indices and sort in descending order.
So we have to take given numbers into an array and one function to calculate all possible prime factor of given number and add all factor and put into the where that number was reside this procedure will be for all the element present in array after that sort the element of array (use any sorting algorithm) in descending order and print them .

SOLUTION:

Setter's Solution 
#include <stdio.h>
#include <math.h>

//Sum of all prime factors
long primeFactorsSum(int num) {
    
    int i;
    long sum = 0;
    
    while (num % 2 == 0) { 
        sum += 2;
        num /= 2; 
    } 
  
    for (i = 3; i <= sqrt(num); i += 2) { 
        while (num % i == 0) { 
            sum += i;
            num /= i; 
        } 
    } 
  
    if (num > 2) 
        sum += num;
        
    return sum;
}


// Insertion sort
void insertionSort(long arr[], int n) {
    
    int i, j, key;
    
    for (i = 1; i < n; i++) { 
        key = arr[i]; 
        j = i - 1; 

        while (j >= 0 && arr[j] > key) { 
            arr[j + 1] = arr[j]; 
            j -= 1; 
        } 
        arr[j + 1] = key; 
    } 
} 


int main(void) {
    
	int test;
	scanf("%d", &test);
	
	while(test--) {
	    int size, i;
	    scanf("%d", &size);
	    
	    int arr[size];
	    long prime_sum[size];
	    
	    for(i = 0; i < size; i++) {
	        scanf("%d", &arr[i]);
	        prime_sum[i] = primeFactorsSum(arr[i]);   //Store elements as sum of all prime factors
	    }
	    
	    insertionSort(prime_sum, size);  //Array sorting
	    
	    //Array printing in reverse order
	    for(i = size-1; i >= 0; i--)
	        printf("%d ", prime_sum[i]);
	    
	    printf("\n");
	}
	
	return 0;
}