Prime factors of LCM of array elements - GeeksforGeeks


Prime factors of LCM of array elements - GeeksforGeeks
Given an array arr[] such that 1 <= arr[i] <= 10^12, the task is to find prime factors of LCM of array elements.

simple solution for this problem is to find LCM of n elements in array. First initialize lcm = 1, then iterate for each element in array and find the lcm of previous result with new element using formula LCM(a, b) = (a * b) / gcd(a, b) i.e., lcm = (lcm * arr[i]) / gcd(lcm, arr[i]). After finding LCM of all n elements we can calculate all prime factors of LCM.
Since here constraint are large, we can not implement above method to solve this problem because while calculating LCM(a, b) we need to calculate a*b and if a,b both are of value 10^12 so it will exceed the limit of integer size. We proceed for this problem in another way using sieve of sundaram and prime factorization of a number. As we know if LCM(a,b) = k so any prime factor of a or b will also be the prime factor of ‘k’.
  • Take a array factor[] of size 10^6 and initialize it with 0 because prime factor of any number are always less than and equal to its square root and in our constraint arr[i] <= 10^12.
  • Generate all primes less than and equal to 10^6 and store them in another array.
  • Now one by one calculate all prime factors of each number in array and mark them as 1 in factor[] array.
  • Now traverse factor[] array and print all indexes which are marked as 1 because these will be prime factors of lcm of n numbers in given array.
const int MAX  = 1000000;
typedef long long int ll;
 
// array to store all prime less than and equal to 10^6
vector <int> primes;
 
// utility function for sieve of sundaram
void sieve()
{
    int n = MAX;
 
    // In general Sieve of Sundaram, produces primes smaller
    // than (2*x + 2) for a number given number x. Since
    // we want primes smaller than n, we reduce n to half
    int nNew = (n)/2;
 
    // This array is used to separate numbers of the form
    // i+j+2ij from others where 1 <= i <= j
    bool marked[nNew + 100];
 
    // Initalize all elements as not marked
    memset(marked, false, sizeof(marked));
 
    // Main logic of Sundaram. Mark all numbers which do not
    // generate prime number by doing 2*i+1
    int tmp=sqrt(n);
    for (int i=1; i<=(tmp-1)/2; i++)
        for (int j=(i*(i+1))<<1; j<=nNew; j=j+2*i+1)
            marked[j] = true;
 
    // Since 2 is a prime number
    primes.push_back(2);
 
    // Print other primes. Remaining primes are of the form
    // 2*i + 1 such that marked[i] is false.
    for (int i=1; i<=nNew; i++)
        if (marked[i] == false)
            primes.push_back(2*i + 1);
}
 
// Function to find prime factors of of n elements of
// given array
void primeLcm(ll arr[], int n )
{
    // factors[] --> array to mark all prime factors of
    // lcm of array elements
    int factors[MAX] = {0};
 
    // One by one calculate prime factors of number
    // and mark them in factors[] array
    for (int i=0; i<n; i++)
    {
        // copy --> duplicate of original element to
        //          perform operation
        ll copy = arr[i];
 
        // sqr --> square root of current number 'copy'
        // because all prime factors are always less
        // than and equal to square root of given number
        int sqr = sqrt(copy);
 
        // check divisibility with prime factor
        for (int j=0; primes[j]<=sqr; j++)
        {
            // if current prime number is factor of 'copy'
            if (copy%primes[j] == 0)
            {
                // divide with current prime factor until
                // it can divide the number
                while (copy%primes[j] == 0)
                    copy = copy/primes[j];
 
                // mark current prime factor as 1 in
                // factors[] array
                factors[primes[j]] = 1;
            }
        }
 
        // After calculating exponents of all prime factors
        // either value of 'copy' will be 1 because of
        // complete divisibility or remaining value of
        // 'copy' will be surely a prime , so we will
        // also mark this prime as a factor
        if (copy > 1)
            factors[copy] = 1;
    }
 
    // if 2 is prime factor of lcm of all elements
    // in given array
    if (factors[2] == 1)
        cout << 2 << " ";
 
    // traverse to print all prime factors of lcm of
    // all elements in given array
    for (int i=3; i<=MAX; i=i+2)
        if (factors[i] == 1)
            cout << i << " ";
}
http://www.geeksforgeeks.org/sieve-sundaram-print-primes-smaller-n/
Read full article from Prime factors of LCM of array elements - GeeksforGeeks

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts