Sieve of Erathonesis for prime factorization
Intuition\nSieve - \n\n# Approach\nUse SPF array\n\n# Complexity\n- Time complexity:\n- \nCalculation of sieve -> O(n log log n)\nStack memory for recursion (ca
# Intuition\nSieve - \n\n# Approach\nUse SPF array\n\n# Complexity\n- Time complexity:\n- \nCalculation of sieve -> O(n log log n)\nStack memory for recursion (can be reduced to O(1) using iterative) - O(1) considering we can convert it to iterative\n\n- Space complexity:\nStorage of sieve O(n)\n\n# Code\n```cpp []\nclass Sieve{\n    const static int a3 = 100050;\n    short int prime[a3 + 1];\n    public:\n    Sieve(int n)\n    {\n        for(int i=0;i<a3;i++){\n            prime[i]=-1;\n        }\n        for (int p = 2; p * p <= n; p++)\n        {\n            if (prime[p] == -1)\n            {\n                for (int i = p * p; i <= n; i += p)\n                    prime[i] = p;\n            }\n        }\n    }\n    int get_min_prime_sum(int n){\n        int _n = n;\n        int suma=0;\n        while(prime[_n]!=-1){\n            suma+=prime[_n];\n            _n /= prime[_n];\n        }\n        suma+=_n;\n        if(suma<n){\n            return get_min_prime_sum(suma);\n        }\n        return suma;\n    }\n};\nSieve * s = new Sieve(100010);\nclass Solution {\npublic:\n    int smallestValue(int n) {\n        return s->get_min_prime_sum(n);\n    }\n};\n```
['C++']